Heap Sort 堆排序

核心结论

堆排序先把数组组织成一个最大堆，随后反复将堆顶最大元素交换到当前未排序区间的末尾，并缩小堆的有效范围。其最好、平均和最坏时间复杂度均为 $\Theta(n\log n)$，辅助空间为 $O(1)$，但通常不稳定。

1. 问题定义

给定一个长度为 $n$ 的可比较元素序列：

$$A = [a_0,a_1,\dots,a_{n-1}],$$

将其重新排列为非递减序列：

$$a'_0 \le a'_1 \le \cdots \le a'_{n-1}.$$

堆排序属于比较排序，主要利用二叉堆维护当前未排序元素中的最大值。

---

2. 前置知识：数组表示的二叉堆

2.1 完全二叉树

二叉堆在逻辑上是一棵完全二叉树，在物理上通常直接存储于数组中，因此不需要显式保存结点指针。

对于 0-based 数组下标，结点 $i$ 的相关位置为：

$$\operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor,$$ $$\operatorname{left}(i)=2i+1,$$ $$\operatorname{right}(i)=2i+2.$$

叶结点范围

在长度为 $n$ 的堆中，最后一个非叶结点的下标为

$$\left\lfloor\frac{n}{2}\right\rfloor-1.$$

因此建堆时只需要从该结点开始向前执行下沉操作。

2.2 最大堆性质

最大堆要求每个结点的值都不小于其孩子结点：

$$A[\operatorname{parent}(i)] \ge A[i], \qquad i>0.$$

因此，最大堆的根结点 $A[0]$ 一定是当前堆中的最大元素。

升序与降序

• 使用最大堆，最终得到升序序列。
• 使用最小堆，最终得到降序序列。

---

3. 基本思想

堆排序将数组划分为两个逻辑区域：

• A[0 : heap_size]：尚未排序的最大堆；
• A[heap_size : n]：已经排好序的后缀。

算法分为两个阶段：

1. 建堆：将整个数组原地调整为最大堆；
2. 反复取最大值：
   • 堆顶 A[0] 是未排序部分的最大值；
   • 将它与未排序部分最后一个元素交换；
   • 缩小 heap_size，把最大值固定在有序后缀；
   • 对新的堆顶执行下沉，恢复最大堆性质。

其关键操作是 MAX-HEAPIFY，也称为向下调整、下沉或 sift down。

---

4. 具体过程

假设输入数组为：

[4, 10, 3, 5, 1]

4.1 阶段一：建立最大堆

从最后一个非叶结点开始，自底向上执行 MAX-HEAPIFY：

原数组：    [4, 10, 3, 5, 1]
最大堆：    [10, 5, 3, 4, 1]

对应的逻辑结构为：

        10
       /  \
      5    3
     / \
    4   1

4.2 阶段二：依次确定最大元素

第一次取出最大值：

交换堆顶和末尾： [1, 5, 3, 4 | 10]
恢复最大堆：     [5, 4, 3, 1 | 10]

第二次取出最大值：

交换：           [1, 4, 3 | 5, 10]
恢复最大堆：     [4, 1, 3 | 5, 10]

第三次取出最大值：

交换：           [3, 1 | 4, 5, 10]

第四次取出最大值：

交换：           [1 | 3, 4, 5, 10]

最终得到：

[1, 3, 4, 5, 10]

其中竖线右侧表示已经排好序、不再属于堆的部分。

---

5. 伪代码

以下伪代码统一使用 0-based 下标，并将 heap_size 定义为堆中有效元素的数量，因此有效下标范围是 [0, heap_size)。

5.1 恢复最大堆性质

MAX-HEAPIFY(A, i, heap_size)
    while true
        left     <- 2 * i + 1
        right    <- 2 * i + 2
        largest  <- i

        if left < heap_size and A[left] > A[largest]
            largest <- left

        if right < heap_size and A[right] > A[largest]
            largest <- right

        if largest = i
            break

        exchange A[i] <-> A[largest]
        i <- largest

前置条件

调用 MAX-HEAPIFY(A, i, heap_size) 时，结点 i 的左右子树应当已经分别满足最大堆性质；只有结点 i 本身可能小于某个孩子。

5.2 建立最大堆

BUILD-MAX-HEAP(A)
    n <- length(A)

    for i <- floor(n / 2) - 1 downto 0
        MAX-HEAPIFY(A, i, n)

5.3 堆排序

HEAP-SORT(A)
    BUILD-MAX-HEAP(A)

    for end <- length(A) - 1 downto 1
        exchange A[0] <-> A[end]
        MAX-HEAPIFY(A, 0, end)

在最后一行中，end 同时表示缩小后的 heap_size，所以已经放到 A[end] 的最大元素不会再次参与堆调整。

---

6. 正确性说明

6.1 MAX-HEAPIFY 的正确性

在左右子树均为最大堆的前提下：

1. 比较结点 i、左孩子和右孩子；
2. 将三者中的最大值交换到结点 i；
3. 若发生交换，只有被交换到下方的结点可能继续违反最大堆性质；
4. 沿该路径继续下沉，直至到达叶结点或不再违反堆性质。

因此，操作结束后，以 i 为根的子树满足最大堆性质。

6.2 建堆的正确性

BUILD-MAX-HEAP 从最后一个非叶结点向根结点处理。

当处理结点 i 时，它的孩子下标均大于 i，对应子树已经在更早的迭代中调整为最大堆。因此，调用 MAX-HEAPIFY 的前置条件成立。处理完根结点后，整个数组构成最大堆。

6.3 堆排序循环不变式

在每轮循环开始时：

1. A[0 : end + 1] 构成最大堆；
2. A[end + 1 : n] 已按非递减顺序排列；
3. 有序后缀中的每个元素都不小于堆中的任意元素。

将堆顶与 A[end] 交换后，未排序部分的最大值被放到正确位置。随后缩小堆并恢复最大堆性质，因此循环不变式继续成立。

当 end = 1 的迭代结束后，堆中只剩一个元素，整个数组已经有序。

---

7. 时空间复杂度

7.1 为什么建堆是 $\Theta(n)$ 而不是 $\Theta(n\log n)$

简单地认为“有 $n$ 个结点，每个结点调整 $O(\log n)$”只能得到一个较松的上界 $O(n\log n)$。

事实上，大多数结点位于树的底部，其下沉距离很短。高度为 $h$ 的结点至多约有 $n/2^{h+1}$ 个，因此建堆总代价满足：

$$T(n) \le \sum_{h=0}^{\lfloor\log n\rfloor} \frac{n}{2^{h+1}}O(h) = O\left( n\sum_{h=0}^{\infty}\frac{h}{2^h} \right) =O(n).$$

同时，建堆至少需要检查线性数量的结点，因此：

$$T(n)=\Theta(n).$$

7.2 算法性质汇总

稳定性

堆排序中的远距离交换可能改变相等关键字的原始相对次序，因此标准堆排序不是稳定排序。例如，带有相同关键字的记录可能在建堆或交换堆顶时跨越彼此。

---

8. 需要问题具有的性质

要直接应用标准堆排序，问题通常需要满足以下条件。

8.1 元素之间存在一致的比较关系

元素应当支持能够确定排序先后的比较规则。理想情况下，该规则应构成全序；在编程语言的排序接口中，通常至少要求比较器满足严格弱序，否则可能得到不一致结果。

8.2 输入可以被重新排列

标准堆排序通过原地交换元素完成排序，因此输入容器必须允许修改。若原始数据不可变，需要先复制到可变序列中。

8.3 适合随机访问

数组能够在 $O(1)$ 时间内通过下标访问父结点和孩子结点，因此最适合实现堆排序。

对于链表，定位下标对应元素通常不是 $O(1)$，会破坏堆排序的效率优势，因此一般不采用数组堆排序。

8.4 不要求稳定排序

若业务要求相同关键字元素保持原始相对顺序，标准堆排序并不适用。可以改用Merge Sort 归并排序等稳定算法，或为元素附加原始下标作为第二关键字，但后者会改变比较对象并增加存储信息。

8.5 希望获得确定的最坏情况上界

堆排序不依赖枢轴选择，其最坏时间复杂度始终为 $\Theta(n\log n)$。当系统更重视最坏情况保证和低额外空间，而不是缓存局部性或稳定性时，堆排序具有优势。

适用场景

堆排序适用于：元素可比较、数据可原地修改、容器支持随机访问、内存受限，并且需要 $O(n\log n)$ 最坏情况保证的排序任务。

---

9. 典型例子

9.1 普通数组升序排序

输入：

[12, 11, 13, 5, 6, 7]

建立最大堆后：

[13, 11, 12, 5, 6, 7]

不断把堆顶移到数组末尾，最终输出：

[5, 6, 7, 11, 12, 13]

9.2 内存受限的比较排序

当数据已经完整存放在数组中，且不能再申请一个 $O(n)$ 的辅助数组时，堆排序可以用 $O(1)$ 辅助空间完成排序，并保持 $\Theta(n\log n)$ 的最坏时间复杂度。

9.3 优先队列与堆排序的联系

最大堆还可实现最大优先队列：

• 查看最大值：$O(1)$；
• 取出最大值：$O(\log n)$；
• 插入元素：$O(\log n)$。

堆排序可以理解为：先用所有元素建成最大优先队列，再连续执行“取出最大值”，但为了原地排序，每次取出的最大值直接放在数组末尾。

注意区分

“使用堆取出最大的 $k$ 个元素”不一定需要完整堆排序。若只需要少量极值，可以根据输入规模和 $k$ 的大小选择大小为 $k$ 的堆、快速选择或其他顺序统计量算法。

---

10. 与常见排序算法对比

---

11. 常见错误

错误 1：混用 0-based 与 1-based 公式

0-based 下标中左、右孩子分别是 2*i + 1 和 2*i + 2；不能直接使用 1-based 的 2*i 和 2*i + 1。

错误 2：交换最大值后没有缩小堆

已经放到数组末尾的最大值必须排除在后续 MAX-HEAPIFY 的有效范围之外。

错误 3：把数组长度与堆大小混为一谈

排序过程中数组长度始终不变，但 heap_size 会逐轮减小。

错误 4：从根结点向下逐个建堆

线性时间建堆应从最后一个非叶结点开始，自底向上调整。若采用逐个插入空堆的方式，建堆时间通常为 $O(n\log n)$。

错误 5：认为堆内部已经完全有序

最大堆只保证父结点不小于孩子结点，并不保证同层结点或左右子树之间整体有序。

---

参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd ed., Chapter 6: Heapsort. MIT Press, 2009.
2. 二叉堆
3. 优先队列
4. 比较排序
5. Obsidian Flavored Markdown Skill