堆排序算法

堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。

堆的定义: 堆是满足下列性质的数列{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    if ( rc.key >= R[j].key )  break; // rc应插入在位置s上

   R[s] = R[j];  s = j;

   }

   R[s] = rc; // 插入

} // HeapAdjust

堆排序的时间复杂度分析：

1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);

2．对n个关键字，建成深度为+1)ûlog2nëh(=的堆，所需进行的关键字比较的次数至多为4n;

3. 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过

+û2(log2(n-1) + …+log22)ûlog2(n-2)ë<log2në2n(

因此，堆排序的时间复杂度为O(nlogn)