1.4 堆排序

这一篇讲堆排序（Heap Sort）。它和归并排序一样是 $O(n\log n)$ ，但有个归并排序没有的优点：原地。不过为了理解堆排序，我们得先认识一个数据结构——堆（heap）。堆本身就是个宝贝，它支撑的"优先队列"是后面 Dijkstra（3.4）、Huffman 编码（3.2）、分支定界（9.7）都要用的零件。

1.堆是什么：披着数组外衣的二叉树

堆是一棵完全二叉树，而且满足堆性质：每个节点的值都 $\ge$ 它两个孩子的值（这叫大顶堆；反过来都 $\le$ 孩子叫小顶堆）。注意堆性质只管"父 $\ge$ 子"，不要求左右孩子之间谁大谁小——这和二叉搜索树（左<父<右）是两码事。

完全二叉树有个好处：它可以用数组紧凑地存下来，不需要指针。把节点按层序（从上到下、从左到右）填进数组，下标从 1 开始：

        A[1]
       /    \
    A[2]    A[3]
    / \     / \
 A[4] A[5] A[6] A[7]

于是给定下标 $i$ ，它的父亲、左孩子、右孩子在数组里的位置可以直接算出来：

\text{PARENT}(i)=\lfloor i/2\rfloor,\quad \text{LEFT}(i)=2i,\quad \text{RIGHT}(i)=2i+1

下标能这么干净地对应，全靠"完全二叉树"这个形状约束——它保证树上没有空洞，层序填进数组严丝合缝。这也是为什么堆操作又快又省内存。

2.堆的核心操作：下沉与上浮

堆有两个最基础的操作，所有别的操作都靠它们拼出来。

下沉（sift-down / heapify）：某个节点可能违反了堆性质（它比孩子小），怎么办？拿它和较大的那个孩子比，如果它比孩子小，就和孩子交换，然后继续往下比，直到它比两个孩子都大、或者沉到底。这一路"沉"下去，路径长度不超过树高 $O(\log n)$ 。

MAX-HEAPIFY(A, i)            // 假设 i 的左右子树都已是堆，只有 i 可能违规
    l = LEFT(i), r = RIGHT(i)
    largest = i
    if l <= heapsize and A[l] > A[largest]: largest = l
    if r <= heapsize and A[r] > A[largest]: largest = r
    if largest != i:
        swap(A[i], A[largest])
        MAX-HEAPIFY(A, largest)   // 继续往下沉

上浮（sift-up）：反过来，某个节点可能比父亲大（在建堆插入新元素时常见），那就和父亲比、交换、继续往上比，直到不超过父亲或到顶。同样 $O(\log n)$ 。

这两个操作是堆的全部秘密。记住它们，后面的一切都好懂。

3.建堆： $O(n)$ 而不是 $O(n\log n)$

给你一个乱序数组，怎么把它调整成一个堆？从最后一个非叶子节点开始，从右往左、从下往上，对每个节点调用一次 MAX-HEAPIFY。

为什么从最后一个非叶子节点开始？因为叶子节点天然满足堆性质（没有孩子可比较），不用动。下标 $>\lfloor n/2\rfloor$ 的都是叶子，所以从 $i=\lfloor n/2\rfloor$ 倒着处理到 $1$ ：

BUILD-MAX-HEAP(A)
    heapsize = n
    for i = ⌊n/2⌋ downto 1:
        MAX-HEAPIFY(A, i)

这里有个反直觉但重要的结论：建堆是 $O(n)$ ，不是 $O(n\log n)$ 。你可能想" $n/2$ 个节点每个下沉 $O(\log n)$ ，不是 $O(n\log n)$ 吗？" 不是，因为大多数节点根本沉不了多深——靠近底部的节点（占绝大多数）只能下沉一两层，只有靠近根的少数节点能沉到 $\log n$ 深。把每层节点数乘上它能下沉的深度加起来，总和是个 $O(n)$ 。4.1 节的递归树/级数分析会严格证明这一点，现在记住：建堆 $O(n)$ ，很便宜。

4.堆排序：反复取出堆顶

建好大顶堆之后，排序就水到渠成了。大顶堆的堆顶 $A[1]$ 是当前最大值。我们把它和数组最后一个元素 $A[n]$ 交换——最大值就归位了。然后把堆的大小减一（把最后那个位置踢出堆），对新的堆顶 $A[1]$ 做一次 MAX-HEAPIFY 修复堆性质。重复，直到堆里只剩一个元素。

HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = n downto 2:
        swap(A[1], A[i])       // 当前最大值放到末尾归位
        heapsize = heapsize - 1 // 缩小堆
        MAX-HEAPIFY(A, 1)       // 修复堆顶

每轮取出最大值、修复堆，修复是 $O(\log n)$ ，做 $n-1$ 轮，所以排序部分 $O(n\log n)$ 。加上建堆的 $O(n)$ ，整体 $O(n\log n)$ 。

最妙的是：整个排序在数组里原地完成，不需要额外空间（除了 $O(1)$ 的几个临时变量）。这是堆排序相对归并排序的大优势——归并要 $O(n)$ 额外空间。

5.堆的另一个身份：优先队列

排序只是堆的一个应用，它更常用的身份是优先队列。优先队列支持两种操作：插入一个元素、取出最大（或最小）元素，且两者都是 $O(\log n)$ 。

INSERT：把新元素放到末尾，然后上浮到正确位置， $O(\log n)$ 。
EXTRACT-MAX：把堆顶拿走，把末尾元素搬到堆顶，再下沉修复， $O(\log n)$ 。

你想想，为什么优先队列这么重要？后面 Dijkstra 算法（3.4）每一步都要"在所有待处理的节点里挑当前距离最短的那个"——这就是个 EXTRACT-MIN。Huffman 编码（3.2）每一步都要"挑两个频率最小的节点合并"——连续的 EXTRACT-MIN。如果没有堆，这些操作都得 $O(n)$ 扫一遍，整个算法就慢一个数量级。堆让"动态维护最大/最小值"这件事变成了 $O(\log n)$ ，这是它能撑起一大票算法的根本原因。

6.三种排序放一起比

到这里我们学了三种排序，把它们摆一起对比，你能看出"没有银弹"这句话的含义：

	插入排序	归并排序	堆排序
最坏时间	$O(n^2)$	$O(n\log n)$	$O(n\log n)$
平均时间	$O(n^2)$	$O(n\log n)$	$O(n\log n)$
最好时间	$O(n)$	$O(n\log n)$	$O(n\log n)$
空间	$O(1)$ 原地	$O(n)$	$O(1)$ 原地
稳定	是	是	否
缓存友好	很好	一般	差（跳跃访问）

堆排序唯一同时做到" $O(n\log n)$ 且原地"，但它不稳定，而且缓存不友好——堆操作在数组里大跨度跳跃访问，没法利用 CPU 缓存的局部性，实际运行往往比同样 $O(n\log n)$ 的归并和快排慢。这就是为什么实际工程里堆排序很少作为通用排序首选，但它的优先队列身份却无处不在。

7.练习

Q1. 给定数组 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]，简述 BUILD-MAX-HEAP 的过程。

数组下标 1..10，叶子是 6..10，从 $i=5$ 倒着到 $i=1$ 逐个 MAX-HEAPIFY。每步修复后堆性质向上传播。最终建成大顶堆 [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]（一种可能的中间形态，具体取决于实现细节）。

Q2. 为什么建堆是 $O(n)$ 而不是 $O(n\log n)$ ？直觉上解释。

因为 $\lfloor n/2\rfloor$ 个节点里，绝大多数是靠近底部的叶子父节点，它们只能下沉 1~2 层；能下沉到 $\log n$ 深的只有靠近根的极少数节点。把"每层的节点数 × 它的最大下沉深度"加起来，总和是个常数倍 $n$ ，所以是 $O(n)$ 。形式证明见 4.1 节。

Q3.（思考题） 堆排序和归并排序都是 $O(n\log n)$ 且都是确定性算法，为什么实际工程普遍更倾向用快排（下一篇 2.1 讲）而不是堆排序作为通用排序？

三个原因：堆排序不稳定；堆操作在数组里大跨度跳跃访问，缓存命中率差，实际常数大；而快排（虽最坏 $O(n^2)$ ）平均 $O(n\log n)$ 、原地、稳定地好、缓存局部性强，实际跑起来通常最快。工程选型不只看渐进复杂度，还看常数、缓存、稳定性——这正是学复杂度分析时要分清"渐进"和"实际"的原因。

8.小结

堆是一种用数组紧凑存储的完全二叉树，靠"下沉"和"上浮"两个 $O(\log n)$ 操作维持堆性质。它带来两样东西：一个原地的 $O(n\log n)$ 堆排序，以及一个无处不在的 $O(\log n)$ 优先队列。记住建堆是 $O(n)$ 这个反直觉的事实，以及堆排序"原地但不稳定、缓存差"的脾性。下一篇我们离开"数组上的算法"，看一种把数据"算"成固定长度指纹的结构——哈希。