堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。
堆的定义:
堆是满足下列性质的数列{r1, r2, …，rn}：
或
若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。
由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。
堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。
堆排序的算法如下所示：
template
void HeapSort ( Elem R[], int n ) {
// 对记录序列R[1..n]进行堆排序。
for ( i=n/2; i>0; --i )
// 把R[1..n]建成大顶堆
HeapAdjust ( R, i, n );
for ( i=n; i>1; --i ) {
R[1]←→R;
// 将堆顶记录和当前未经排序子序列
// R[1..i]中最后一个记录相互交换
HeapAdjust(R, 1, i-1);
// 将R[1..i-1] 重新调整为大顶堆
}
} // HeapSort
其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。
Template
void HeapAdjust (Elem R[], int s, int m) {
// 已知R[s..m]中记录的关键字除R[s].key之
// 外均满足堆的定义，本函数调整R[s] 的关
// 键字，使R[s..m]成为一个大顶堆（对其中
// 记录的关键字而言）
rc = R[s];
for ( j=2*s; j<=m; j*=2 ) {// 沿key较大的孩子结点向下筛选
if ( j
本文地址：http://com.8s8s.com/it/it34121.htm