二叉堆是优先队列很普遍的一种实现，它又分为最小堆最大堆，最小堆和最大堆都是完全二叉树。
其结构体定义如下：
struct HeapStruct {
int Capacity; //堆的最大容量
int Size; //堆的当前结点数
ElementType *Elements; //存放堆结点的数组
}
typedef struct HeapStruct *PriorityQueue;
二叉堆的结点可以保存在一个数组中。
1、如果从数组的索引1开始存放堆结点，那么对于数组中任意位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i + 1)中
2、如果从数组的索引0开始存放堆结点，那么对于数组中任意位置i上的元素，其左儿子在位置(2i+1)上，右儿子在左儿子后的单元(2i+2)中。
在下面的代码中，统一采用第一种方式存放堆结点。你可以通过下面的代码注意到，用第一种方式给编程带来的好处。
最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
（1）插入操作Insert，采用制造“空穴”，上滤的方式——“空穴”在堆中不断上移直到找出正确的位置。插入操作复杂度O(logN)。
void Insert(ElementType X, PriorityQueue H) {
int i;
if( IsFull(H) ) { //判断堆是否已满
Error( "Priority queue is full" );
return ;
}
for( i = ++ H->Size; H->Elements[i/2] > X; i = i/2) {
H->Elements[i] = H->Elements[i/2] ;
}
H->Elements[i] = X ;
}
（2）删除最小元素(即根�结点)DeleteMin，下滤的方式。删除最小元素操作的复杂度O(logN)，因为删除后涉及重建堆。
ElementType DeleteMin(PriorityQueue H) {
int i, Child ;
ElementType MinElement, LastElement;
if( IsEmpty(H) ) { //判断堆是否为空
Error( "Priority queue is empty" );
return H->Elements[0];
}
MinElement = H->Elements[1];
LastElement = H->Elements[H->Size--]; //在�根结点删除了第一个堆结点，因此在根结点制造了一个“空穴”，
先保存最后一个堆结点，堆大小减1。下面的�代码是把LastElement放到合适的地方。
for( i =1; i*2 <= H->Size; i= Child) { //下滤过程
//找较小的一个儿子结点
Child = i * 2; //左儿子结点
if(Child != H->Size && H->Elements[Child + 1] < H->Elements[Child] )
Child++; //如果左儿子不是新堆的最后一个结点，且左儿子大于右儿子，我们选择右儿子
//判断较小的儿子结点是否小于LastElement。若是，把该较小的儿子结点上移到自己的父结点；
//若不是，退出循环。（即LastElement比儿子结点都小，可以作为它们的父结点插入）
if(LastElement > H->Elements[Child] )
H->Elements[i] = H->Elements[Child];
else
break;
}
H->Elements[i] = LastElement ;
return MinElement; //返回被删除的根节点
}
（3）如果仅仅是�要获得最小值，那么可以在常数时间完成O(1)。
</br>
最大堆：父结点的键值总是�大于或等于任何一个子节点的键值。
（1）插入操作Insert，采用制造“空穴”，上滤的方式——“空穴”在堆中不断上移直到找出正确的位置。插入操作复杂度O(logN)。
void Insert(ElementType X, PriorityQueue H) {
int i ;
if( IsFull(H) ) {
Error( "Priority queue is full" );
return ;
}
for(i=++H->Size; H->Elements[i/2] < X; i = i/2) {
H->Elements[i] = H->Elements[i/2];
}
H->Elements[i] = X;
}
对比最小堆的插入操作，可看到只是把for循环的条件">X"改为"<X"。意思是只要X比它的父结点大，就一直上滤。
（2）删除最大元素(即根�结点)DeleteMax，下滤的方式。删除最大元素操作的复杂度O(logN)，因为删除后涉及重建堆。
ElementType DeleteMax(PriorityQueue H) {
int i, Child;
ElementType MaxElement, LastElement;
if( IsEmpty(H) ) {
Error( "Priority queue is empty" );
return H->Elements[0];
}
MaxElement = H->Elements[1];
LastElement = H->Elements[H->Size--];
for(i=1; 2*i <=H-Size; i = Child) {
Child = i*2;
* if(Child != H->Size && H->Elements[Child+1] > H->Elements[Child])
Child++;
* if(LastElement < H->Elements[Child] )
H->Elements[i] = H->Elements[Child];
else
break;
}
H->Elements[i] = LastElement;
return MaxElement;
}
与最小堆的删除最小元素操作相比，有2处条件判断发生改变，已用*号标出，读者可以自行体会。
（3）如果仅仅是要获得最大值，那么可以在常数时间完成O(1)。
</br>
二叉堆的应用——堆排序：
用最大堆完成堆排序，每次DeleteMax花费时间O(logN)，对N个元素进行排序就是O(NlogN)。
另外建立二叉堆花费的时间为O(N)。不解可参考->《为什么堆排序构建堆的时间复杂度是N》
所以堆排序的时间复杂度为O(NlogN)+O(N) = O(NlogN)，因为是就地排序，所以空间复杂度为O(1)。
void HeapAdjust(int *a, int i, int size) { //调整堆
int Child;
int tmp;
for(tmp = a[i]; 2*i+1 < size; i = Child) {
Child = 2*i+1; //左儿子
if(Child != size-1 && a[Child+1] > a[Child]) //如果右儿子比左儿子大，取右儿子
Child++;
if(tmp < a[Child])
a[i] = a[Child];
else
break;
}
a[i] = tmp;
}
void HeapSort(int *a, int size) { //堆排序主例程
int i;
for(i = size/2; i>=0; i--) { //构建堆
HeapAdjust(a, i, size);
}
for(i = size-1; i>0; i--) {
int temp = a[i]; //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
a[i] = a[0];
a[0] = temp;
HeapAdjust(a, 0, i); //重新调整堆顶节点成为大顶堆
}
}
注：堆排序代码的堆结点从数组索引0开始
