最大堆性质：A[PARENT(i)]>=A[i]
最小堆性质：A[PARENT(i)]<=A[i]
（注意：这里的i是除了根结点以外的所有结点）
如果把堆看成一棵树，可以定义一个堆中的结点的高度就是结点到叶结点最长简单路径上边的个数，因而可以把堆的高度定义为根结点的高度。故此，我们可以得到：
一个具有n个元素的堆的高度为logn；
高度为h的堆中，元素个数最多为2^(h+1)-1个，元素个数最少为2^h个。
因此，我们可以联想到，最大堆通过将根元素提取到结尾几乎可以对应到降序排列，而最小堆通过将根元素提取到结尾几乎可以对应到升序排列。下面我们使用最大堆来讨论。
堆的元素处理
根据堆的三个重要的属性，我们可以得到父结点和子结点的获取方法，下面用C语言实现：
首先定义数组大小
#define N 6
/*
返回父节点和子节点索引
*/
//返回父结点
int parent(int index)
{
return (index-1)/2;
}
//返回左孩子
int left(int index)
{
return (index<<1)+1;
}
//返回右孩子
int right(int index)
{
return (index+1)<<1;
}
堆的性质维护
由于要满足最大堆的性质，因此当添加一个新元素时，我们需要让它满足父结点大于子结点的性质，故堆的性质需要我们去维护，因而，当我们检查结点i是否满足要求时，我们应该检查结点i是否比它的孩子结点都要大，如果比它们大，则可以不用操作；反之，应该将该结点与孩子结点进行交换到新的结点上，进而再次检查该新结点是否满足要求，操作方法同上，直到该结点没有孩子结点为止。
维护堆的性质基本思路如上所述，下面用C语言实现：
/*
维护堆的性质，即把不符合要求的元素重新组织
时间复杂度为logn
*/
void maxHeapify(int *A,int index,int size)
{
int L=left(index);
int R=right(index);
int tmp;
int largestIndex=index;
if(L<size && *(A+index)<*(A+L)) {
largestIndex=L;
}
if(R<size && *(A+largestIndex)<*(A+R)) {
largestIndex=R;
}
if(index!=largestIndex) {
tmp=*(A+index);
*(A+index)=*(A+largestIndex);
*(A+largestIndex)=tmp;
maxHeapify(A,largestIndex);
}
}
如上所示，维护堆的时间复杂度为堆的高度成正比，即logn。类似的，也可以编写一个minHeapify函数来实现最小堆。
堆的建立
堆的建立即使堆的每个元素都能满足最大堆的性质的要求，因为叶子结点没有孩子结点，因而叶子结点无法调用maxHeapify函数，故每个叶子结点都可以看成一个只包含一个元素的堆。
堆的建立可以使用以下一段C语言代码来实现：
/*
对除没有子结点的结点进行堆的维护操作，进而
使得一个数组变成一个最大堆
时间复杂度为nlogn
*/
void buildMaxHeap(int *A)
{
int size=N;
//找出不是叶子结点的最后一个索引
int need=size/2-1;
int i;
for(i=need;i>=0;i--) {
maxHeapify(A,i,size);
}
}
类似的，可以编写一个buildMinHeap来建立最小堆。
堆排序算法
通过上面的步骤，我们已经把一个数组建立成为一个最大堆，然而最大堆并不一定是有序堆，因为最大堆只保证了父结点大于子结点，并没有保证左孩子一定大于右孩子，因此，堆排序就是要使左孩子大于右孩子。但是，我们始终相信，根元素是最大的，因此，我们想先找最大的比较方便，把最大的元素先扔到结尾的叶子结点上，而之前的叶子结点将跑到根结点上并且要满足堆的性质进行维护即可。
据此，我们可以设计如下算法来实现：
/*
堆排序程序
通过根元素始终是最大的，因此我们倒过来找
从最大的元素依次往最小的元素去排序
*/
void heapSort(int *A)
{
buildMaxHeap(A);
int size=N;
int i;
int tmp;
for(i=size-1;i>=0;i--) {
tmp=*A;
*A=*(A+i);
*(A+i)=tmp;
size--;
maxHeapify(A,0,size);
}
}
因此堆排序的时间复杂度为nlogn。
运行实例
int main()
{
int a[N]={2,1,3,2,5,4};
heapSort(a);
int i;
for(i=0;i<N;i++) {
printf("%d ",a[i]);
}
return 0;
}
堆排序算法的意义
堆排序是一种优秀的算法，尽管快速排序的算法性能要优于堆排序，但是堆这一数据结构仍然有重要的实际应用——高校的优先队列，实际问题例如如何动态保留成绩在倒数100名的学生的信息。
张泽旺 深度学习每日摘要
智造家