优先队列：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。采用数组或链表实现优先队列。
最大堆和最小堆：从根节点到任意结点路径上结点序列的有序性
typedef struct HeapStruct *MaxHeap; struct HeapStruct { ElementType *Elements; //存储堆元素的数组 int size; //堆的当前元素个数 int capacity; //堆的最大容量 };
最大堆的创建
MaxHeap Create ( int MaxSize ) { //创建容量为MaxSize的空的最大堆 MaxHeap H = malloc(sizeof(struct HeapStruct)); H->Elements = malloc( (MaxSize+1) * sizeof(ElementType) ); H->size = 0; H->capacity = MaxSize;
H->Elements[0] = MaxData; //定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作 return H; }
插入：将新增节点插入到从其父结点到根结点的有序序列中
void Insert ( MaxHeap H, ElementType item ) { //将元素item插入最大堆H，其中H->Elements[0]已经定义为哨兵 int i; if ( IsFull(H) ) { printf("最大堆已满"); return; } i = ++H->Size; //i指向插入后堆中的最后一个元素的位置 for ( ; H->Elements[i/2]<item; i/=2 ) { //父结点是i/2 H->Elements[i] = H->Elements[i/2]; //向下过滤结点 } H->Elements[i] = item; //将item插入 }
for循环中，H->Element[0]是哨兵元素，它不小于堆中的最大元素，可以控制循环结束
时间复杂度T(N) = O(log N);
删除：
ElementType DeleteMax ( MaxHeap H ) { //从最大堆H中取出键值为最大的元素，并删除一个结点 int Parent, Child; ElementType MaxItem, temp; if ( IsEmpty(H) ) { printf("最大堆已为空"); return; } 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++; //目的：Child指向左右子结点的较大者 if ( temp >= H->Elements[Child] ) break; else //移动temp元素到下一层 H->Elements[Parent] = H->Elements[Child]; } H->Elements[Parent] = temp; return MaxItem; }
Parent*2<=H->Size：判别是否有左儿子
(H->Elements[Child] < H->Elements[Child+1])：左右儿子比较
时间复杂度T(N) = O(log N);
最大堆的建立：将已经存在的N个元素按最大堆的要求存放在一个一位数组中
方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为O(N logN);
方法2：在线性时间复杂度下建立最大堆。
（1）将N个元素按输入顺序存入，先满足完全二叉树的结构特性
（2）调整各结点位置，以满足最大堆的有序特性
建堆时间复杂性：O(n) 树中各结点的高度和
// 判断最小堆是否已满
bool isFull(MinHeap* minHeap) { if (minHeap->size == minHeap->capacity) { return true; } return false; }
// 判断最小堆是否为空
bool isEmpty(MinHeap* minHeap) { if (minHeap->size == 0) { return true; } return false; }