数据结构之堆排序

  对于几个元素的关键字序列{K₁，K₂，…，K_n}，当且仅当满足下列关系时称其为堆，其中 2i 和2i+1应不大于n。
{ K i ≤ K 2 i + 1 K i ≤ K 2 i 或 { K i ≥ K 2 i + 1 K i ≥ K 2 i {\huge \{}^{K_i≤K_{2i}} _{K_i≤K_{2i+1}} \quad\quad 或 \quad\quad {\huge \{}^{K_i≥K_{2i}} _{K_i≥K_{2i+1}} {Ki​≤K2i+1​Ki​≤K2i​​或{Ki​≥K2i+1​Ki​≥K2i​​
  若将此序列对应的一维数组(即以一维数组作为序列的存储结构)看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不小于(或不大子) 其左、右孩子,结点的值。因此，在一个堆中，堆顶元素(即完全二义树的根结点)必为序列中的最大元素(或最小元素)，并且堆中的任一棵子树也都是堆。若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。
  推排序的基本思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列(即建立初始堆)，从而可以输出堆项的最大关键字(对于大根堆而言)，然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。
  初始堆的建立方法是：将待排序的关键字分放到一棵完全二叉树的各个结点中(此时完全二叉树并不一定具备堆的特性)，显然，所有 i> $[\frac{n}{2}]$的结点 K_i 都没有子结点，以这样的 K_i 为根的子树已经是堆，因此初始建堆可从完全二叉树的第 i {i=$[\frac{n}{2}]$} 个结点 K_i 开始，通过调整，逐步使以K[$\frac{n}{2}$]、K[$\frac{n}{2}$]-1、K[$\frac{n}{2}$]-2、…、K₂、K₁为根的子树满足堆的定义。
  在对K_i 为根的子树建堆的过程中，可能需要交换 K_i 与K_2i 或(K_2i+1)的值，如此一来，以K_2i(或K_2i+i)为根的子树可能不再满足堆的定义，则应继续以 K_2i(或K_2i+1)为根进行调整。如此层层地递推下去，可能会一直延伸到叶子结点时为止。这种方法就像过筛子一样，把最大(或最小)的关键字一层一层地筛选出来，最后输出堆顶的最大(或最小) 元素。
  【函数】将一个整型数组中的元素调整成大根堆。

void HeapAdjust(int data[], int s, int m)
/*在 data[s..m]所构成的一个元素序列中，除了 data[s]外，其余元素均满足大顶堆的定义*/
/*调整元素 data[s]的位置，使 data[s..m]成为一个大顶堆*/
{int tmp,j;tmp = data[s];							/*备份元素 data[s]，为其找到适当位置后再插入*/for(j= 2*s+1; j<=m; j=j*2+1){			/*沿值较大的孩子结点向下筛选*/if(j<m && data[j]<data[j+1]) ++j;	/*j是值较大的元素的下标*/if(tmp>=data[i]) break;data[s] = data[jl; s =j;			/*用s记录待插入元素的位置 (下标) */}/*for*/data[s]=tmp;							/*将备份元素插入由 s 所指出的插入位置*/
}/*HeapAdjust*/

  调整成新堆：假设输出堆顶元素之后，以堆中最后一个元素替代，那么根结点的左、右子树均为堆，此时只需自上至下进行调整即可。
  【函数】用堆排序方法对整型数组进行非递减排序。

void HeapSort(int data[], int n)		/*数组 data[0..n-1]中的n个元素进行堆排序*/
{inti;int tmp;for(i = n/2-1; i>=0; --i)			/*将 data[0..n-1]调整为大根堆*/HeapAdjust(data, i, n-1);for(i= n-l; i>0; --i){tmp=data[0]; data[0]=data[i];data[i] = tmp;					/*堆顶元素 data[0]与序列末的元素 data[i]交换*/HeapAdjust(data,0,i-1);			/*待排元素的个数减 1，将 data[0..i-1]重新调整为大根堆*/}/*for*/
}/*HeapSort*/

  为序列(55,60,40,10,80,65,15,5,75)建立初始大根堆的过程如下图所示

  调整为新堆过程如下图所示

  对于记录数较少的文件来说，堆排序的优越性并不明显，但对子大量的记录来说，堆排序是很有效的。堆排序的整个算法时间是山建立初始堆和不断调整堆这两部分时同构成的。可以证明，堆排序算法的时间复杂度为 O(n ㏒ n)。此外，堆排序只需要一个记录大小的辅助空间。堆排序是一种不稳定的排序方法。