完全二叉树建堆优先队列代码

二叉搜索树建堆（优先队列）代码，数据存放在动态申请的数组内。主要操作有，创建、插入、删除、调整等。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

// 梁笔记

// https://zouzhongliang.com

#include <stdlib.h>

#include <stdio.h>

typedef struct HeapStruct* Heap;

typedef int ElementType;

struct HeapStruct{

ElementType *Elements; //存储堆元素的数组

int Size; //堆的当前元素个数

int Capacity; //堆的最大容量

};

typedef Heap MaxHeap; /* 最大堆 */

typedef Heap MinHeap; /* 最小堆 */

#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */

MaxHeap Creat(int MaxSize)

{ //创建容量为MaxSize的空最大堆

MaxHeap H = malloc(sizeof( HeapStruct));

H->Elements = malloc( (MaxSize+1) * sizeof(ElementType) );

H->Size = 0;

H->Capacity = MaxSize;

H->Elements[0] = MAXDATA;//定义“哨兵”

return H;

}

bool IsFull(MaxHeap H)

{

return H->Size == H->Capacity;

}

void Insert(MaxHeap H,ElementType item)

{

int i;

if( IsFull(H)){

printf("最大堆已满");

}

i = ++H->Size; //指向插入后堆中的最后一个元素的位置

for(; H->Elements[i/2] < item; i/=2){

H->Elements[i] = H->Elements[i/2]; //向下过滤结点

}

H->Elements[i] = item;

}

bool IsEmpty(MaxHeap H)

{

return H->Size == 0;

}

#define ERROR -1

ElementType DeleteMax(MaxHeap H)

{

int Parent, Child;

ElementType MaxItem, temp;

if(IsEmpty(H)){

printf("最大堆已为空");

return ERROR;

}

MaxItem = H->Elements[1]; //取出结点最大值

temp = H->Elements[H->Size--];

for(Parent = 1;Parent*2<=H->Size;Parent=Child){

Child = Parent*2;

if( (Child!=H->Size) &&

(H->Elements[Child] < H->Elements[Child+1]) )

Child++;

if (temp >= H->Elements[Child]) break;

else

H->Elements[Parent] = H->Elements[Child];

}

H->Elements[Parent] = temp;

return MaxItem;

}

/*----------- 建造最大堆 -----------*/

void PercDown( MaxHeap H, int p )

{ /* 下滤：将H中以H->Elements[p]为根的子堆调整为最大堆 */

int Parent, Child;

ElementType X;

X = H->Elements[p]; /* 取出根结点存放的值 */

for( Parent=p; Parent*2<=H->Size; Parent=Child ) {

Child = Parent * 2;

if( (Child!=H->Size) && (H->Elements[Child]<H->Elements[Child+1]) )

Child++; /* Child指向左右子结点的较大者 */

if( X >= H->Elements[Child] ) break; /* 找到了合适位置 */

else /* 下滤X */

H->Elements[Parent] = H->Elements[Child];

}

H->Elements[Parent] = X;

}

void BuildHeap( MaxHeap H )

{ /* 调整H->Data[]中的元素，使满足最大堆的有序性 */

/* 这里假设所有H->Size个元素已经存在H->Elements[]中 */

int i;

/* 从最后一个结点的父节点开始，到根结点1 */

for( i = H->Size/2; i>0; i-- )

PercDown( H, i );

}

void FreeHeap(MaxHeap H)

{

free(H->Elements);

}

相关文章: