上一篇博客，我们讲到了选择排序的简单选择排序，这篇博客，我们就来讲一下选择排序的另外一种排序——堆排序。
（一）堆
那么堆是什么呢？堆其实是一棵顺序存储的完全二叉树。堆一般采用数组来进行存储。堆分为最大堆和最小堆。
每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为最小堆。
每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为最大堆。
（二）堆排序
堆的概念很好理解。那我们再来看一下堆排序的过程。下面以最大堆为例。
（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为最大堆。
依次输出，直至最后一个元素，这个数组就是从小到大排列的了。
光说过程可能就抽象了，下面我们上图！
以{ 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }为例。
首先，我们要构造这个无序序列为最大堆。
过程如下图：
此时，最大堆已构造完成。下面就是堆排序了。
只要依次输出，然后调整，再输出，循环往复，堆排序就完成了。
（三）核心代码
堆排序的算法描述如下：
void HeapSor(List R){
int i;
for (i=n/2;i>=1;i--){
Shit(R,i,n); //从第n/2个记录开始进行筛选建堆
}
for (i=n;i>=2;i--){
swap(R[1],R[i]); //将堆顶记录和最后一个记录互换
Shit(R,1,i-1); //调整R[1]使剩余元素变成堆
}
}
