数据结构（邓俊辉）学习笔记】优先级队列 07——堆排序

1.算法

作为完全二叉堆的一个应用，这节来介绍堆排序算法。

是的，谈到优先级队列，我们很自然地就会联想到排序。因为就其功能而言，包括完全二叉堆在内的任何一种优先级队列都天生地具有选取功能，也就是选取其中的最大元。因此，很自然地就会联想起选择排序。

还记得这样一幅插图（上图中右上图），我们曾经用它来解释选择排序的原理及过程。不妨温习一下，在选择排序算法中，我们始终将整个序列分为两部分，也就是左侧的待排序部分以及右侧的已排序部分。而且前者中的任何一个元素都不大于后者中的任何一个元素。因此我们只需反复地遍历待排序元素，从中选取出最大者，并将它加入到已排序的子序列中。是的，正因为我们每次都需要对待排序的部分作遍历，从而导致每次选取都需要线性的时间，以致整个算法累计需要平方量级的时间。

究其原因，可以理解为我们当初对数据结构的理解和掌握还非常有限，以至于我们只能借助简单的数据结构来组织待排序的元素。而经过了一段时间的学习之后，我们已经今非昔比，我们可以运用更为高级的数据结构来组织这些待排序的元素，从而实现更高的选取效率。

比如，联想到我们刚刚学过的内容，很自然地就会想到用一个完全二叉堆来取代此前简单的线性结构。如果暂时忽略底层的具体实现，我们就会发现整个算法流程可以基本保持不变。

1. 此前在与预处理阶段对整个线性序列的初始化，在这里则对应于建堆操作。我们刚刚介绍过，如果采用 Floyd 算法，这一步只需线性的时间。
2. 接下来我们需要反复地取出最大元，也就是整个堆当前的堆顶。我们知道， delMax操作每次只需 log n 的时间。没错，log n 而不再是 n。因此，整个算法的复杂度，也就应该是 n log n，而不再是 $n^2$。

当然，此前的不变性依然保持，也就是待排序的部分始终都不超过已排序部分，因此算法的正确性依然可以得到保证。那么难道这个算法就是这样的平淡无奇？不是的，事实上堆排序的奥妙还不止于此，比如在空间复杂度方面，堆排序算法还可以做得更好。

2.就地

准确地讲，在空间复杂度方面，我们希望堆排序算法能够做到就地，也就是除了输入数据以外，只需要常数的辅助空间。 这种构思是有可能实现的，因为我们注意到，所谓的完全二叉堆在物理上就是不折不扣的向量。

因此我们或许可以令完全二叉堆与已排序的部分在同一个向量中和平共处，经过精巧的设计，我们的确可以将这一构想兑现为这种形式，具体来说，已排序部分依然居于向量的后端，而与之互补的前缀则恰好构成一个完全二叉堆，如果沿用大顶堆的惯例，我们可以立即发现，堆中的最大元必然始终都是0号元素，而接下来需要与之兑换的 X，则必然是相对于已排序元素而言秩为 -1 的那个元素。

按照以上堆排序的初始版本，我们首先需要取出这个最大的元素，然后用 x 来取而代之，然后再将备份的最大元植入 x 这个位置。当然，为了算法能够继续持续下去，我们还需要对新的根节点做下滤调整。

对于这样的连续4步操作，你能发现有什么可以优化的地方吗？
是的，这里的1、2、3完全可以整合起来，只需 m 和 x 之间的一次兑换即可等效地完成。因此，算法过程中的每一步迭代可以进一步的规整为两大步骤，也就是第一步交换，以及第二步下滤。是的，反复地交换下滤，交换下滤。直至堆变空。在整个算法的过程中，除了交需要用到常数个辅助空间之外，我们并不需要任何更多的辅助空间。

以上过程可以描述为这样的伪代码（上图最下面行），但是它又如何进一步地实现为真正的代码呢？

3.实现

在这里，给出堆排序的一个更为通用的算法版本，也就是说对于任何的向量，这个算法都可以对其中任意指定的区间进行排序。

1. 作为初始化，首先需要调用完成二叉堆的建堆算法，在线性的时间内，将向量的这个区间整理为一个完全二叉堆。
2. 此后进入反复迭代，请留意这个迭代所具有的不变性，也就是完全二叉堆当前所在的区间是由 lo 和 hi 界定的，按照我们一直以来采用的惯例，lo 所对应的是堆的首元素，而 hi 所指示的则是这个堆尾部的哨兵。

因此在每一步迭代中，我们都只需取出首元素位置处的最大元，并且将它与末元素交换，而新的堆顶元素的下滤功能则同样是由 delMax 在底层完成。

4.实例

看堆排序算法的一个具体实例，考察这样一个规模为 5 的向量，首先从逻辑上将它视作为一棵完全二叉树，其中有两个内部节点，也就是2和4，于是我们采用 Floyd 算法分别对 2 和 4分别做一趟下滤，即可最终得到这样一个完全二叉堆。至此，也就完成了算法的预处理步骤。

接下来我们进入算法的主体循环，请注意在一开始整个向量都是未排序的部分，而已排序的部分初始为空。即便如此，我们依然可以使用算法的基本策略，也就是令当前的堆顶与末元素互换位置。

1. 破坏之后的瞬间应该是这样（上图上左二）。原来的末元素2成为了堆顶，而5则在逻辑上从原来的堆中分离出来，加入原本为空的 S。也就是说，已排序的序列此时已经拥有了第一个元素。

2. 当然，我们还需要对新的堆顶做下滤调整，从而使得剩下的 4 个元素依然恢复为一个堆，尽管规模减少了一个单位。不出意外，接下来的最大元 4 也自然成为了新的堆顶（上图上左三）。

3. 因此在下一轮迭代中，我们依然是将这个新的堆顶与当前的末元素互换位置，在逻辑上这等效于将堆顶摘出，并归入到有序序列中（上图下左一）。

4. 同样，我们仍需对新的根节点做一次下滤调整，从而使得剩余的三个元素能够继续保持为是一个合法的大顶堆（上图下左三）。
   

5. 不出预料，当前尚未排序的元素中的最大者 3 此时也必然就是堆顶。因此,我们也只需令它与当前的末元素 2 做一次兑换。在逻辑上，这依然等同于将这个堆顶摘出并归入到有序列中。

6. 此后再经过一轮下滤调整，剩余的元素也依然会恢复为一个合法的大顶堆，尽管此时已经只剩最后的两个元素了。