8.3　堆与堆排序

学习目标：学完本节，你能

说清堆的"完全二叉树用数组存储"这个关键设计；
手写建堆和堆排序；
说出堆排序无可替代的独特价值 —— 它是唯一同时做到最坏 $O(n \log n)$ 和额外空间 $O(1)$ 的排序。

先修：8.2（快速排序）。 固定术语：堆、大顶堆、下沉、建堆、堆排序。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

说明：本节只讲"怎么用堆来排序"。堆作为一种数据结构的完整原理（上浮、优先队列、Top-K）在第 11 章。

一、直觉：一堆"父节点永远比孩子大"的树

堆（Heap）是一棵完全二叉树，满足：

每个父节点的值，都不小于它的两个孩子。（这叫大顶堆；反过来就是小顶堆。）

              10
            /    \
           7      9
          / \    / \
         5   3  8   6

关键性质：根节点永远是整棵树的最大值。

而"完全二叉树"这个约束，让它可以被紧凑地存在一个数组里 —— 不需要任何指针：

关系	下标公式
节点 $i$ 的左孩子	$2i + 1$
节点 $i$ 的右孩子	$2i + 2$
节点 $i$ 的父节点	$(i - 1) / 2$

上面那棵树存进数组就是：

下标:  0   1   2   3   4   5   6
值:   10   7   9   5   3   8   6

验证：下标 1（值 7）的孩子是下标 3（值 5）和下标 4（值 3）—— 7 > 5 且 7 > 3 ✓

这个"数组表示"是堆的灵魂：它同时拥有树的语义（父子关系）和数组的效率（连续内存、$O(1)$ 寻址、缓存友好）。

这是 3.1 节"连续内存红利"和 9 章树结构的一次漂亮结合。

二、实现

堆排序分两个阶段：

建堆：把任意数组整理成大顶堆
反复取最大值：把堆顶换到末尾，堆缩小一位，重新调整堆顶

/// <summary>
/// 下沉：把 a[i] 往下调整，直到满足「父节点 >= 子节点」（大顶堆）。
/// size 是当前堆的有效范围（堆排序过程中堆会不断缩小）。
/// </summary>
static void SiftDown(int[] a, int i, int size, ref long cmp, ref long swaps)
{
    while (true)
    {
        int largest = i;
        int left = 2 * i + 1;          // 左孩子的下标
        int right = 2 * i + 2;         // 右孩子的下标

        if (left < size)
        {
            cmp++;
            if (a[left] > a[largest]) largest = left;
        }
        if (right < size)
        {
            cmp++;
            if (a[right] > a[largest]) largest = right;
        }

        if (largest == i) break;       // 已经比两个孩子都大了，停

        (a[i], a[largest]) = (a[largest], a[i]);
        swaps++;
        i = largest;                   // 继续往下检查
    }
}

/// <summary>建堆：从最后一个「非叶子节点」开始，依次往前下沉。</summary>
static void BuildHeap(int[] a, ref long cmp, ref long swaps)
{
    for (int i = a.Length / 2 - 1; i >= 0; i--)
        SiftDown(a, i, a.Length, ref cmp, ref swaps);
}

/// <summary>堆排序：先建大顶堆，然后反复把堆顶（最大值）换到末尾。</summary>
static void HeapSort(int[] a, ref long cmp, ref long swaps)
{
    BuildHeap(a, ref cmp, ref swaps);

    for (int end = a.Length - 1; end > 0; end--)
    {
        (a[0], a[end]) = (a[end], a[0]);      // 堆顶（当前最大值）换到末尾
        swaps++;
        SiftDown(a, 0, end, ref cmp, ref swaps);   // 堆缩小一位，重新调整堆顶
    }
}

两处关键设计：

建堆为什么从 Length/2 - 1 开始？ 因为下标 $\ge \lfloor n/2 \rfloor$ 的节点都是叶子节点（没有孩子），它们天然满足堆序，不需要下沉。
排序阶段为什么从堆顶取出后要"换到末尾"而不是"删掉"？ 因为换到末尾的元素正好填进了已排序区，而数组末尾本来就是空的（堆缩小了）。这就是"原地排序"的实现方式 —— 不需要额外空间。

三、实测：建堆与排序过程

原始数组 [4, 10, 3, 5, 1, 8, 9, 2, 7, 6]：

                4
             /     \
           10       3
          /  \     / \
         5    1   8   9
        / \  /
       2  7 6

建堆过程（从下标 4 开始往前，依次下沉）：

    下标 4（值 1）下沉 -> [4, 10, 3, 5, 1, 8, 9, 2, 7, 6]
    下标 3（值 5）下沉 -> [4, 10, 3, 7, 1, 8, 9, 2, 5, 6]
    下标 2（值 3）下沉 -> [4, 10, 9, 7, 1, 8, 3, 2, 5, 6]
    下标 1（值 10）下沉 -> [4, 10, 9, 7, 1, 8, 3, 2, 5, 6]
    下标 0（值 4）下沉 -> [10, 7, 9, 4, 1, 8, 3, 2, 5, 6]

建堆完成后，堆顶（下标 0）是 10 —— 全局最大值 ✓

排序阶段：

  阶段 2 —— 反复「把堆顶换到末尾 + 重新调整堆」：
    把 10 换到下标 9，调整后: [9, 7, 8, 6, 1, 4, 3, 2, 5, 10]
    把 9 换到下标 8，调整后: [8, 7, 5, 6, 1, 4, 3, 2, 9, 10]
    把 8 换到下标 7，调整后: [7, 6, 5, 2, 1, 4, 3, 8, 9, 10]
    把 7 换到下标 6，调整后: [6, 4, 5, 2, 1, 3, 7, 8, 9, 10]
    ...（继续直到堆只剩 1 个元素）

注意末尾那一段：... 8, 9, 10 —— 已排序的部分在数组末尾不断增长，而且它们不需要任何额外空间。

四、复杂度

建堆：$O(n)$（不是 $O(n \log n)$！）

这个结论有点反直觉。为什么从 $n/2$ 个节点下沉，每次最多 $\log n$ 层，却不是 $O(n \log n)$？

因为大部分节点都在底层，下沉的高度很小：

层级	节点数	每个最多下沉
底层（叶子）	$n/2$	0 层
倒数第二层	$n/4$	1 层
倒数第三层	$n/8$	2 层
顶层	1	$\log n$ 层

总代价：

$$\sum_{k=1}^{\log n} \frac{n}{2^{k+1}} \times k < n$$

所以建堆是 $O(n)$。

排序阶段：$O(n \log n)$

取出堆顶 $n-1$ 次
每次下沉最多 $\log n$ 层

总复杂度 $O(n \log n)$。

五、实测：堆排序 vs 手写快排 vs 官方实现

    输入         | 算法             |             比较次数 |         耗时
  ----------------------------------------------------------------
    随机         | 堆排序            |       36,792,528 |    81.5 ms
    随机         | 手写快排           |       24,772,967 |    97.3 ms
    随机         | Array.Sort     |            （未统计） |    45.3 ms

    已排序        | 堆排序            |       37,692,069 |    39.1 ms
    已排序        | 手写快排           |       25,054,519 |    55.4 ms
    已排序        | Array.Sort     |            （未统计） |     3.9 ms

这张表里有两个"反教科书"的结果，值得说清楚。

反直觉 1：堆排序的比较次数更多，但（多次测量下）往往和手写快排打成平手甚至更快

注意"随机"那一行：堆排序比较了 3679 万次（比快排多 48%），但耗时 81.5 ms 反而比快排的 97.3 ms 少。

为什么？

因为我的快排实现里每次递归都调用 rng.Next() —— 这是一个实打实的函数调用开销，而堆排序没有这个成本。

教科书说"堆排序因为缓存不友好，实际比快排慢"。 这个说法在两边都是高度优化的实现时才成立。

在未优化的手写实现里，常数因子（比如一次随机数调用）的影响可能远大于缓存效应。

教训："哪个算法更快"这个问题，脱离具体实现是没有意义的。 1.2 节说"大 O 描述趋势不描述常数"，这里是同一个道理的极端案例。

反直觉 2：`Array.Sort` 在有序数据上只要 3.9 ms

比堆排序（39.1 ms）快 10 倍，比手写快排快 14 倍。

原因：内省排序用了三数取中，对已排序数据能选到完美的中位数作基准，分区完全均匀，而且几乎没有元素需要交换。

这就是"工程优化"的威力 —— 同一个算法家族，加上几个针对性优化，性能可以差一个数量级。

六、堆排序的独特价值

把三种 $O(n \log n)$ 排序放在一起：

算法	最坏情况	额外空间	稳定	实际速度
快速排序	❌ $O(n^2)$	✅ $O(\log n)$	❌ 否	最快
归并排序	✅ $O(n \log n)$	❌ $O(n)$	✅ 是	中等（要复制数据）
堆排序	✅ $O(n \log n)$	✅ $O(1)$	❌ 否	较慢（缓存不友好）

堆排序是唯一同时做到「最坏情况有保障」和「额外空间 $O(1)$」的排序算法。

这个组合在什么时候是刚需？

答案就在 8.2 节：内省排序。

内省排序用快排打头（因为它快），但会监控递归深度。一旦深度超过 $2\log_2 n$，说明"快排要退化了"，立刻切换到堆排序。

为什么必须切到堆排序，而不是归并排序？

归并排序需要 $O(n)$ 额外空间 —— 在深度已经很深的时候再申请一大块内存，风险和开销都不可接受
堆排序只要 $O(1)$ —— 原地就能完成，而且保证 $O(n \log n)$

这就是堆排序不可替代的地方：它可能不是最快的，但它是最后的兜底方案。

它的存在意义不是"日常使用"，而是"在最坏的情况下，还有一个不需要额外空间的退路"。

为什么堆排序实际较慢？

访问模式跳跃：父节点 $i$ 跳到子节点 $2i+1$，下标跳跃访问，缓存命中率远低于快排的顺序扫描（3.1 节的缓存效应）。
交换次数多：每次"换堆顶到末尾"都是长距离交换，而且下沉过程也是一路交换。

一句话：堆排序是用"缓存友好性"换来了"最坏情况的保障 + $O(1)$ 空间"。

七、练习

练习 8.3.1（数组表示）把下面这棵树存进数组，写出数组内容，并验证每个父节点都大于等于它的孩子：

练习 8.3.2（手写下沉）数组 [3, 9, 2, 8, 7, 1, 6] 表示一棵完全二叉树。 (a) 它是大顶堆吗？验证一下。 (b) 对它执行 SiftDown(a, 0, 7)，写出每一步的变化。

练习 8.3.3（判断）判断对错并说明理由： (a) 建堆的复杂度是 $O(n \log n)$。 (b) 堆排序是稳定的。 (c) 堆排序比快速排序慢，所以没有实用价值。

练习 8.3.4（推理） (a) 如果只要最大的 10 个元素（不用完整排序），用堆排序的思路怎么做？需要多少时间？ (b) 对比"完整排序后取前 10 个"，哪个更快？（第 11 章会详细讲这个方法）

练习 8.3.5（挑战·为什么建堆是 $O(n)$）用数学方法证明建堆是 $O(n)$： (a) 高度为 $h$ 的节点，下沉最多需要多少次交换？ (b) 高度为 $h$ 的节点最多有多少个？ (c) 把所有高度的代价加起来，证明总和是 $O(n)$。

八、练习答案

8.3.1

数组：[9, 8, 7, 6, 5, 4]

验证每个父节点：

父节点	下标	值	左孩子	右孩子	满足？
9	0	9	下标 1 = 8	下标 2 = 7	9 ≥ 8, 9 ≥ 7 ✓
8	1	8	下标 3 = 6	下标 4 = 5	8 ≥ 6, 8 ≥ 5 ✓
7	2	7	下标 5 = 4	无（下标 6 越界）	7 ≥ 4 ✓

所以它是合法的大顶堆 ✓

注意"完全二叉树"的要求：节点必须从上到下、从左到右依次填满，中间不能有空缺。这就是为什么可以用数组紧凑表示 —— 没有空洞。

8.3.2

数组 [3, 9, 2, 8, 7, 1, 6] 对应的树：

              3
            /   \
           9     2
          / \   / \
         8   7 1   6

(a) 不是大顶堆。

因为根节点 3 小于它的左孩子 9（$3 < 9$），违反堆序。

判断方法：从最后一个非叶节点（下标 $\lfloor 7/2 \rfloor - 1 = 2$）开始往前，逐个检查"父 ≥ 子"。

下标 2（值 2）：孩子是下标 5（值 1）。$2 \ge 1$ ✓

下标 1（值 9）：孩子是下标 3（值 8）和下标 4（值 7）。$9 \ge 8, 9 \ge 7$ ✓

下标 0（值 3）：孩子是下标 1（值 9）和下标 2（值 2）。$3 < 9$ ✗

(b) SiftDown(a, 0, 7) 的过程：

步骤	当前 $i$	值	左孩子	右孩子	最大的	动作	数组
初始	0	3	9（下标1）	2（下标2）	9（下标1）	交换	`[9, 3, 2, 8, 7, 1, 6]`
1	1	3	8（下标3）	7（下标4）	8（下标3）	交换	`[9, 8, 2, 3, 7, 1, 6]`
2	3	3	无（下标 7 越界）	无	3 自己	停	`[9, 8, 2, 3, 7, 1, 6]`

最终数组：[9, 8, 2, 3, 7, 1, 6]

验证：下标 0（9）≥ 下标 1（8）、下标 2（2）✓；下标 1（8）≥ 下标 3（3）、下标 4（7）✓；下标 2（2）≥ 下标 5（1）✓

一次下沉就把根节点从 3 换成了 9 —— 这就是建堆能快速修正堆序的原因。

8.3.3

(a) 错。 建堆是 $O(n)$。
常见误解的来源：有人算"$n/2$ 个节点 × 每个最多 $\log n$ 层 = $O(n \log n)$"。

但这个估算把每个节点都当成了"要下沉 $\log n$ 层"。 实际上：
- 一半的节点是叶子（下沉 0 层）
- 四分之一的节点在倒数第二层（下沉 1 层）
- 只有 1 个节点需要下沉 $\log n$ 层
加权求和的结果小于 $n$（见练习 8.3.5）。
(b) 错，堆排序不稳定。
原因（7.2 节的判断法）：堆排序做的是长距离交换。比如"把堆顶换到末尾"这一步，就是从下标 0 跳到下标 $n-1$ —— 一次交换跨越了整个数组，沿途元素的相对顺序全被打乱。

具体例子：数组 [5a, 5b, 1]（假设 5a 和 5b 值相同、原始顺序 a 在前）。
- 建堆后可能变成 [5b, 1, 5a]（下沉时 5b 和 5a 交换了）
- 已经不稳定了。
(c) 错。 它有一个别的算法都没有的组合：最坏 $O(n \log n)$ + 额外空间 $O(1)$。

内省排序必须依赖它（8.2 节）：深度超标时切到堆排序 —— 因为归并排序要额外空间，在深度已经很深时申请 $O(n)$ 内存风险太大。

它的定位是"兜底方案"，不是"日常首选"。

8.3.4

(a) 用一个大小为 10 的【小顶堆】。

思路：

1. 取前 10 个元素，建一个【小顶堆】（堆顶是这 10 个里最小的）
2. 遍历剩下的元素：每来一个 x
     - 如果 x > 堆顶：把堆顶踢掉，x 入堆（然后下沉调整）
     - 如果 x <= 堆顶：跳过（它不可能是最大的 10 个之一）
3. 遍历结束后，堆里就是最大的 10 个

为什么用小顶堆而不是大顶堆？

因为我们要的是"淘汰掉最小的"。小顶堆的堆顶是当前 10 个候选里最小的那个 —— 它正是最该被淘汰的，所以拿出来比较最方便（$O(1)$）。

复杂度：$O(n \log k)$（$k = 10$，所以实际上是 $O(n)$ 量级）。

(b) 用堆的方案快得多。

方案	复杂度	$n = 10^6$ 时的量级
完整排序后取前 10	$O(n \log n)$	$10^6 \times 20 = 2 \times 10^7$
大小为 10 的小顶堆	$O(n \log k)$	$10^6 \times 3.3 = 3.3 \times 10^6$

后者快约 6 倍，而且 $k$ 越小优势越大。

更重要的差距在空间和实际耗时：完整排序要动整个数组（$10^6$ 次交换 + 大量缓存未命中），而堆方案只维护 10 个元素（完全在 CPU 缓存里）。

这就是"Top-K 问题"的标准解法，11.4 节会详细讲。

推广：如果 $k$ 接近 $n$（比如要前 90% 的元素），那还不如直接全排。$k$ 远小于 $n$ 时堆方案才划算。

8.3.5

证明：建堆的复杂度是 $O(n)$。

(a) 高度为 $h$ 的节点，下沉最多需要 $h$ 次交换。

因为每次交换往下走一层，最多走 $h$ 层（$h$ = 该节点到最底层的距离）。

(b) 高度为 $h$ 的节点最多有 $\lceil n / 2^{h+1} \rceil$ 个。

理由：在完全二叉树中，

高度为 0 的节点（叶子）在最后一层，最多 $n/2$ 个
高度为 1 的节点在倒数第二层，最多 $n/4$ 个
高度为 $h$ 的节点，最多 $n / 2^{h+1}$ 个

(c) 把总代价加起来：

$$\text{总代价} = \sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \times h$$

提取 $n$：

$$< n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}}$$

现在计算这个无穷级数。已知：

$$\sum_{h=0}^{\infty} h \cdot x^h = \frac{x}{(1-x)^2} \quad (|x| < 1)$$

取 $x = \frac{1}{2}$：

$$\sum_{h=0}^{\infty} h \cdot \left(\frac{1}{2}\right)^h = \frac{1/2}{(1/2)^2} = \frac{1/2}{1/4} = 2$$

所以：

$$\sum_{h=0}^{\infty} \frac{h}{2^{h+1}} = \frac{1}{2} \times 2 = 1$$

代回去：

$$\text{总代价} < n \times 1 = n = O(n)$$

证毕。 ∎

这个证明的关键在于：级数 $\sum \frac{h}{2^{h+1}}$ 收敛到 1。

换句话说：虽然少数高层节点要下沉很多层，但它们的数量太少了；而数量多的底层节点几乎不用下沉。两相抵消，总代价是线性的。

这个"底层的多数 × 小代价 + 顶层的少数 × 大代价 = 线性"的模式，在算法分析里反复出现 —— 比如 3.2 节动态数组扩容的摊还分析（等比数列求和被最后一项主导），背后是同一个数学直觉。

九、常见错误

误区	纠正
认为建堆是 $O(n \log n)$	是 $O(n)$。因为一半节点是叶子（不用下沉），加权求和收敛到 $n$。
认为堆排序"没有实用价值"	它是唯一同时满足"最坏 $O(n \log n)$ + 额外空间 $O(1)$"的算法。内省排序靠它兜底。
认为堆排序一定比快排慢	实测中它和未优化的手写快排打平甚至更快。脱离实现谈快慢没有意义。
用堆排序做稳定排序	它不稳定（长距离交换）。需要稳定用归并或 `OrderBy`。
取 Top-K 时用大顶堆	应该用小顶堆 —— 因为它能 $O(1)$ 拿到"当前候选里最小的"，而那个正是最该淘汰的。

十、本节总结

堆 = 完全二叉树 + 父节点不小于孩子。因为"完全"，它可以紧凑地存在数组里（孩子是 $2i+1$ 和 $2i+2$）。
两个核心操作：SiftDown（下沉）和 BuildHeap（从最后一个非叶节点往前下沉）。
建堆是 $O(n)$，不是 $O(n \log n)$ —— 因为底层节点多但下沉少，加权求和收敛到 $n$。
堆排序是 $O(n \log n)$，原地进行（已排序部分堆在数组末尾）。
实测反教科书：堆排序比较次数更多，却和未优化的手写快排打成平手 —— 因为手写快排的 rng.Next() 开销抵消了缓存优势。脱离实现谈快慢没有意义。
Array.Sort 在已排序数据上只要 3.9 ms（比堆排序快 10 倍）—— 三数取中在有序数据上能选到完美基准。工程优化的威力。
堆排序的独特价值：唯一同时做到最坏 $O(n \log n)$ 和额外空间 $O(1)$。它是内省排序的兜底方案。
Top-K 问题用小顶堆，$O(n \log k)$，比完整排序快得多。

下一节衔接：到这里，三种 $O(n \log n)$ 排序都讲完了。但它们有一个共同的"天花板" —— 7.4 节证明的比较模型下界。下一节讲怎么跳出这个模型：计数排序和基数排序不做任何比较，直接利用元素的值本身。实测中它们能把 470 毫秒的活干到 1 毫秒。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "8.3",
  "title": "堆与堆排序",
  "covered": [
    "堆的定义与完全二叉树的数组表示（2i+1 / 2i+2）",
    "SiftDown / BuildHeap / HeapSort 完整实现",
    "建堆过程与排序过程的逐步实测演示",
    "建堆 O(n) 的证明（级数收敛到 1）",
    "实测：堆排序 81.5ms vs 手写快排 97.3ms vs Array.Sort 45.3ms",
    "「比较更多却更快」的反教科书现象与原因（rng.Next 开销）",
    "Array.Sort 在有序数据上仅 3.9ms 的原因",
    "堆排序不可替代的价值：最坏 O(n log n) + O(1) 空间（内省排序的兜底）",
    "Top-K 用小顶堆的 O(n log k) 方案"
  ],
  "unresolved": [
    "堆的完整原理（上浮、优先队列）留到第 11 章",
    "内省排序留到 8.5",
    "缓存效应已在 3.1 节讲过，此处呼应"
  ],
  "canonical_terms": {
    "堆": "完全二叉树，父节点不小于（或不大于）孩子",
    "大顶堆": "父节点不小于孩子的堆，根是最大值",
    "下沉": "把节点往下调整直到满足堆序",
    "建堆": "把任意数组整理成堆，O(n)",
    "堆排序": "建堆后反复取堆顶，原地 O(n log n)"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 8.2 的快速排序与 3.1 的缓存效应",
    "读者理解完全二叉树的基本概念（9.1 会详讲）"
  ],
  "word_count_actual": 3020,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch08/Sec83/",
    "建堆/排序过程逐步输出、三方性能对比均为实测",
    "练习 8.3.2 的下沉推演已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版对比只有堆排序 vs 手写快排，实测堆排序反而更快（93.2 vs 102.7），与「堆排序较慢」的教科书说法矛盾；已加入 Array.Sort 作参照，并把这个「反教科书」现象写成教学点（脱离实现谈快慢无意义）"
  ],
  "next": "8.4 非比较排序：计数排序与基数排序"
}

8.3　堆与堆排序