8.4.2　堆排序

1.堆排序的基本思想

堆排序是另一种基于选择的排序方法。下面我们先介绍一下什么是堆，然后再介绍如何利用堆进行排序。

由n个元素组成的序列｛k1，k2，…，kn－1，kn｝，当且仅当满足如下关系时：（1）ki≤k2i或ki≥k2i其中i＝1，2，3，…，n／2；（2）ki≤k2i＋1 ki≥k2i＋1，称为堆。

例如，序列（47，35，27，26，18，7，13，19）满足：

即对任意ki（i＝1，2，3，4）有：ki≥k2iki≥k2i＋1，所以这个序列就是一个堆。

若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列｛k1，k2，…，kn）是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。例如，下列两个序列为堆，｛96，83，27，38，11，09｝和｛12，36，24，85，47，30，53，91｝对应的完全二叉树如图8－11所示。

图8－11 堆的示例

下面我们讨论一下如何利用堆进行排序：从堆的定义可以看出，若将堆用一棵完全二叉树表示，则根结点是当前堆中所有结点的最小者（或最大者）。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小（或次大）的记录，依此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。

2.堆排序的基本问题

既然堆顶元素（关键字）是最小元素，那么它是排序序列的最小元素，输出后，将其他元素再调整成堆，新的堆顶元素是排序序列的第二个元素。如此下去，通过堆，可将一个无序序列变为一个有序序列。因此，堆排序的基本问题是：

（1）如何由一个无序序列建成一个堆？

（2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

堆排序过程如图8－12所示。

图8－12 堆排序过程

图8－12 堆排序过程（续）

3.堆排序算法

将最后一个元素和堆顶元素交换（相当于将堆顶元素输出）后，这时，从堆顶到倒数第二元素，除堆顶元素外，其余元素均符合堆的定义。下面采用筛选法，把包括堆顶元素在内的所有元素调成堆。

从代码中也可以看出，整个排序过程分为两个for循环。第一个循环要完成的就是将现在的待排序序列构建成一个大顶堆。第二个循环要完成的就是逐步将每个最大值的根结点与末尾元素交换，并且再调整其成为大顶堆。

算法8.10 堆排序算法

我们所谓的将待排序的序列构建成为一个大顶堆，其实就是从下往上，从右到左，将每个非终端结点（非叶结点）当作根结点，将其和其子树调整成大顶堆，下面的算法即调整大顶堆的算法。

算法8.11 建立大根堆

4.堆排序算法分析

堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。对深度为k的堆，筛选算法中进行的关键字比较次数至多为2（k－1）次，则在建含n个元素、深度为h的堆时，总共进行的关键字比较次数不超过4n。n个结点的完全二叉树的深度为Llog2n＋1，则调整建新堆时调用HeapAdjust过程n－1次，总共进行的比较次数不超过下式之值：

由此，堆排序因为整个排序过程中需要调用n－1次堆顶点的调整，而每次堆排序算法本身耗时为log2n，其时间复杂度也为O（nlog2n），属于最坏的情形；堆排序对小文件效果不明显，但对大文件有效，相对于快速排序来说，这是堆排序最大的优点。此外，堆排序仅在第二个for循环中交换记录时用到一个临时变量temp，其空间效率为O（1）。

堆排序中，除建初堆以外，其余调整堆的过程最多需要比较树深度的n＋1次，因此与简单选择排序相比时间效率提高了很多；另外，不管原始记录如何排列，堆排序的比较次数变化不大，所以说堆排序对原始记录的排列状态并不敏感。

在堆排序算法中只需要一个暂存被筛选记录内容的单元和两个简单变量h和i，所以堆排序是一种速度快且省空间的排序方法。堆排序是一种不稳定的排序方法。