4.12. 堆排序¶
4.12.1. 堆排序¶
我们对快速排序的讨论是从考虑用 BST 排序的实用性开始的。 BST 比其他排序方法需要更多空间，而且由于向树中插入值的成本相对较高，它会比快速排序或归并排序更慢。 BST 也有可能变得不平衡，从而导致 \(\Theta(n^2)\) 的最坏情况运行时间。 BST 中的子树平衡与快速排序的划分步骤密切相关。快速排序的枢轴所起的作用大致相当于 BST 的根值：左划分（子树）存储小于枢轴（根值）的值，而右划分（子树）存储大于或等于枢轴（根值）的值。
我们可以基于一种更适合该用途的树结构，设计出一个好的排序算法。具体来说，我们希望这棵树是平衡的、空间高效的且快速的。该算法应当利用这样一个事实：排序是一种专用应用，所有待存储的值在开始时就已经全部可用。这意味着我们不一定需要一次一个地把值插入树结构中。
堆排序 基于
堆 数据结构。
堆排序具备刚才列出的全部优点。
完全二叉树是平衡的，其数组表示是空间高效的，而且我们可以一次性把所有值
装入树中，从而利用高效的 buildheap 函数。
当所有记录的键值都唯一时，堆排序在最好、平均和最坏情况下的渐近性能
都是 \(\Theta(n \log n)\) 。
它在平均情况下不如快速排序快（相差一个常数因子），但堆排序有一些特殊
性质，使它特别适用于
外排序
算法，用于对大到无法装入主存的数据集进行排序。
完整实现如下。
下面是一个堆排序热身练习。
4.12.2. 堆排序熟练度练习¶
现在测试一下你对堆排序的理解程度。你能重现它的行为吗？
4.12.3. 堆排序分析¶
这个可视化展示了堆排序的运行时间分析。
虽然堆排序通常比快速排序慢一个常数因子
（因为用 removemax 卸下堆比快速排序的一系列划分要稍慢一些），
但堆排序相比目前研究过的其他排序有一个特殊优势。
建堆相对廉价，只需 \(\Theta(n)\) 时间。
从堆中删除最大值的记录在最坏情况下需要 \(\Theta(\log n)\) 时间。
因此，如果我们想找出数组中键值最大的 \(k\) 条记录，可以在
\(\Theta(n + k \log n)\) 时间内完成。
如果 \(k\) 很小，这比用前面介绍的其他排序方法找出 \(k\) 条最大
值记录所需的时间有显著改进（其中许多方法都需要先对整个数组排序）。
有一种情形可以利用这个概念，那就是
Kruskal 算法
在 最小生成树 的实现中。
该算法要求按升序访问各条边（因此要使用最小堆），但一旦 MST 构建完成，
这个过程就立即停止。
因此，只需对相对较小一部分边进行排序。
另一种特殊情况是，所有待排序记录的键值都相同。这代表了堆排序的最好情况。这是因为删除最大值只需常数时间，因为被交换到顶部的值永远不会沿堆向下筛选（由于所有键值都相等）。这一过程会重复进行，以常数时间从堆中删除 \(n\) 个元素，因此最好情况总时间为 \(\Theta(n)\) 。
