堆：优先队列，取出元素的顺序根据元素的优先级，而非进入队列的先后顺序。
#include "sdtio.h" #include "stdlib.h" typedef struct HeapStruct *MaxHeap; struct HeapStruct{ ElementType *Elements; int Size; int Capacity; } /* 最大堆的创建 */ MaxHeap Create(int MaxSize) { MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct)); Elements = malloc(sizeof(ElementType)*(MaxSize+1)); H->size = 0; H->Capacity = MaxSize; H->Elements[0] = MaxData; } /* 判断堆满 */ int IsFull(MaxHeap H) { return (H->Size == H->Capacity); } /* 判断堆空 */ int IsEmpty(MaxHeap H) { return H->Size == 0; } /*插入元素*/ void Insert(MaxHeap H,ElementType item) { int i; if( IsFull(H) ){ printf("MaxHeap is Full\n"); return; } i = ++H->Size; for(; H->Elements[i/2] <item;i/=2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = item; } /*删除最大值（根结点）*/ ElementType Delete(MaxHeap H) { int Parent,Child; ElementType MaxItem,temp; if( IsEmpty(H)){ printf("Heap is Empty\n"); return; } MaxItem = H->Elements[1]; //取出最大值 temp = H->Elements[H->Size--]; //用堆中最后元素从根节点开始通过逐级下降的方法过滤结点 for(Parent = 1;Parent*2 <= H->Size;Parent = Child){ // Parent*2<=H->Size 判断是否有子结点 Child = Parent*2; //默认指向左孩子 if(Child! H->Size && H->Elements[Child] < H->Elements[Child+1]) Child++; //判断是否有右孩子，如有并且右孩子元素值大，则指向右孩子 //（如果Child != H->Size，则意味着Child<H->Size,则需要比较左，右，temp三个值的大小） if(temp >= H->Elements[Child]) break; //temp值和较大值比较，如果temp大，则temp作为父节点 else H->Elements[Parent] = H->Elements[Chlid]; // 否则，子节点较大值作为父节点 } H->Elements[Parent] = temp; return MaxItem; } /* 建造最大堆*/ void PercDown( MaxHeap H, int p ) { /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */ int Parent, Child; ElementType X; X = H->Data[p]; /* 取出根结点存放的值 */ for( Parent=p; Parent*2<=H->Size; Parent=Child ) { Child = Parent * 2; if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) ) Child++; /* Child指向左右子结点的较大者 */ if( X >= H->Data[Child] ) break; /* 找到了合适位置 */ else /* 下滤X */ H->Data[Parent] = H->Data[Child]; } H->Data[Parent] = X; } void BuildHeap( MaxHeap H ) { /* 调整H->Data[]中的元素，使满足最大堆的有序性 */ /* 这里假设所有H->Size个元素已经存在H->Data[]中 */ int i; /* 从最后一个结点的父节点开始，到根结点1 */ for( i = H->Size/2; i>0; i-- ) PercDown( H, i ); }