第 11 章　堆与优先队列

本章解决的问题：怎么在"不断有数据进出"的情况下，始终 O(1) 拿到最大/最小的那个？

11.1　堆的定义与数组表示

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

• 说清"堆序"这个比全局有序弱得多的约束，以及它为什么够用；
• 用父子下标公式在数组和树之间自由换算；
• 说出堆为什么用数组实现是"严格更优"而不是"图省事"。

先修：9.1（树的术语）、3.1（连续内存）。 固定术语：堆、堆序、小顶堆、大顶堆、完全二叉树。 环境与版本：.NET 8 / C# 12。 预计阅读：26 分钟。

和 8.3 节的关系：8.3 节用堆来排序（讲了建堆和下沉）。本节把堆当作数据结构来讲 —— 聚焦它的定义、表示和"为什么这样设计"。堆排序只是堆的一个副产品。

一、直觉：两种不同的"有序"

先破除一个常见误解：堆不是"排好序的数组"。

实测对比：

  堆的数组表示: [2, 5, 3, 8, 7, 6]
  层序遍历就是数组顺序: 2 5 3 8 7 6

  如果按【从小到大】排序，应该是: 2 3 5 6 7 8

  堆的数组顺序   : 2 5 3 8 7 6
  完全排序的顺序 : 2 3 5 6 7 8

注意 3 排在 5 后面 —— 但 $3 < 5$。所以堆显然不是有序的。

那堆保证了什么？它只保证一件事：

任何一个父节点，都小于等于它的两个孩子。

就这么简单。这个约束比"全局有序"弱得多：

关键洞察：如果业务只需要"每次拿出最小的那个"，那"父子有序"这个弱约束就够了。

堆就是"用刚好够用的有序性，换取廉价的维护代价"。

这个思路在算法设计里反复出现 —— 比如 10.1 节的 BST 也是"用部分有序信息换取查找加速"。

二、堆的定义

堆 = 完全二叉树 + 堆序性质。

               2
             /   \
            5     3
           / \   /
          8   7 6

两个条件缺一不可：

实测验证这个堆：

  一个合法的小顶堆：
          2
      5       3
    8     7     6

  存进数组就是: [2, 5, 3, 8, 7, 6]

  验证父子关系（用下标公式算）：
    下标 0（值 2）的孩子是下标 1、2（值 5、3）
      检查：2 <= 5 ✓   2 <= 3 ✓
    下标 1（值 5）的孩子是下标 3、4（值 8、7）
      检查：5 <= 8 ✓   5 <= 7 ✓
    下标 2（值 3）的孩子是下标 5（值 6）
      检查：3 <= 6 ✓

  结论：这是一个合法的小顶堆：True

注意第 ① 条"完全二叉树"是必需的。 如果树有空洞，下面讲的"数组表示"就不成立了（会有下标对不上）。

8.3 节的堆排序用的也是这个结构 —— 那里讲了下沉和建堆，本节聚焦"定义和表示"。

三、数组表示与下标公式

因为"完全二叉树"这个约束，堆可以紧凑地存在数组里 —— 不需要任何指针。

换算公式（必须记住）：

实测验证：

      下标 i |      值 |        左孩子下标 |        右孩子下标 | 父节点下标
  --------------------------------------------------------------
         0 |      2 |        1（值5） |        2（值3） | 无（它是根）
         1 |      5 |        3（值8） |        4（值7） | 0（值2）
         2 |      3 |        5（值6） |            无 | 0（值2）
         3 |      8 |            无 |            无 | 1（值5）
         4 |      7 |            无 |            无 | 1（值5）
         5 |      6 |            无 |            无 | 2（值3）

注意"父节点 = $(i-1)/2$"用的是整除：

    i=1 -> (1-1)/2 = 0     i=2 -> (2-1)/2 = 0    （1 和 2 的父都是 0）
    i=3 -> (3-1)/2 = 1     i=4 -> (4-1)/2 = 1    （3 和 4 的父都是 1）

这个公式为什么成立？

因为完全二叉树是按层从左到右编号的。第 $k$ 层的第一个节点编号是 $2^k - 1$，而它前面正好有 $2^k - 1$ 个节点 —— 两个孩子的编号正好是父亲编号的"两倍加一/加二"。

你不需要记推导，但要知道"这个公式成立的前提是完全二叉树" —— 普通二叉树用不了数组表示。

四、为什么用数组而不是链表

"用数组表示树"听起来像是一种取巧，但实际上它在这里是严格更优的选择。

原因是堆同时满足两个特殊条件：

1. 它是完全二叉树 —— 层序编号和数组下标一一对应，没有空洞浪费
2. 它不需要在中途插入/删除 —— 只在末尾加、只在根上删

第 2 条往往被忽略，但它同样关键：

堆的所有操作都只在两个位置进行 —— 数组末尾（插入）和下标 0（取最小）。

而这两个位置在数组里都是 $O(1)$ 可达的。

对比链表实现：

    维度                   | 数组实现                | 链表实现
    ------------------------------------------------------------------------
    每节点额外内存           | 0（紧凑排列）            | 约 16 字节（两个指针）
    缓存友好性              | 好（连续内存）            | 差（节点散落）
    找父/子节点             | O(1) 下标计算            | 需要额外维护父指针

所以堆的数组实现不是"省事"，而是【严格更优】。

这是 3.1 节"连续内存红利"的又一次体现 —— 你在第 6 章（哈希表）、第 8 章（堆排序）都见过同一个主题。

"树结构要连续存储"这件事，只有在数据结构本身提供了足够强的约束时才做得到 —— 堆的"完全二叉树"约束就是那个前提。

五、大顶堆 vs 小顶堆

把堆序反过来，就得到另一种堆：

实测大顶堆：

  同一批数据，组织成大顶堆：
          9
      7       8
    3     5     6

  数组表示: [9, 7, 8, 3, 5, 6]
  性质：每个父节点 >= 孩子，根是【最大值】9
  验证：是合法的大顶堆 ✓

一个容易搞混的点："找最大的 K 个"用的是小顶堆，不是大顶堆。

原因在 11.4 节详细讲 —— 简单说：小顶堆的根是"当前候选里最小的那个"，而那个恰好是最该被淘汰的，所以拿它来比较最方便。

六、练习

练习 11.1.1（下标计算） 一个堆的数组是 [1, 3, 2, 7, 5, 4]。 (a) 画出这棵完全二叉树。 (b) 下标 3 的节点的父节点是谁？值是多少？ (c) 下标 2 的节点有几个孩子？分别是多少？ (d) 它是小顶堆吗？验证一下。

练习 11.1.2（反向推理） 一个堆有 10 个节点（下标 0~9）。 (a) 最后一个非叶节点的下标是多少？ (b) 下标 4 的节点，是叶子还是内部节点？ (c) 下标 5 呢？

练习 11.1.3（判断） 判断对错并说明理由： (a) 堆的数组表示是按"层序遍历"排列的。 (b) 堆是一种有序结构，因为它能快速找到最小/最大值。 (c) 既然是树，堆用链表实现会更自然。 (d) 大顶堆的数组从大到小排列。

练习 11.1.4（设计） 你要实现一个"任务调度器"，任务有优先级，每次取优先级最高的执行。 (a) 应该用大顶堆还是小顶堆？ (b) 如果用数组实现，插入新任务时应该放在哪里？ (c) 取出最高优先级任务后，数组会变成什么样？要怎么恢复堆序？

练习 11.1.5（挑战·d 叉堆） 二叉堆每个节点有 2 个孩子。能不能搞"三叉堆"或"d 叉堆"？ (a) 对下标 $i$ 的节点，它的孩子下标是什么？父节点呢？ (b) d 叉堆的高度是多少（用 $n$ 和 $d$ 表示）？ (c) 增大 $d$ 有什么好处和坏处？

七、练习答案

11.1.1

数组 [1, 3, 2, 7, 5, 4]：

(a) 完全二叉树：

          1
        /   \
       3     2
      / \   /
     7   5 4

(b) 下标 3 的父节点 = $(3-1)/2 = 1$。

父节点是下标 1，值是 3。

(c) 下标 2 的孩子：左 = $2 \times 2 + 1 = 5$，右 = $2 \times 2 + 2 = 6$。

下标 6 越界（数组只有 6 个元素，下标 0~5），所以只有 1 个孩子 —— 下标 5，值是 4。

(d) 是小顶堆。

全部通过 ✓

注意 (c) 的细节："有 2 个孩子"要看下标是否越界，不能只看公式。

判断"下标 $i$ 是不是叶子"的快速方法：$i > n/2 - 1$ 就是叶子。

本例 $n = 6$，$n/2 - 1 = 2$。所以下标 3、4、5 都是叶子，下标 0、1、2 是内部节点 ✓

11.1.2

$n = 10$（下标 0~9）。

(a) 最后一个非叶节点的下标 = $\lfloor n/2 \rfloor - 1 = 5 - 1 = 4$。

下标 4。

(b) 下标 4 是内部节点（就是 (a) 求出的那个最后非叶节点）。

验证：下标 4 的孩子是 $2 \times 4 + 1 = 9$ 和 $2 \times 4 + 2 = 10$。下标 9 存在（$< 10$），下标 10 越界。所以它有 1 个孩子 ✓

(c) 下标 5 是叶子。

验证：孩子下标是 11 和 12，都越界 ✓

记忆规则：

对于有 $n$ 个节点的完全二叉树（下标 0~$n-1$）：

• 下标 $\le \lfloor n/2 \rfloor - 1$ 的是内部节点
• 下标 $> \lfloor n/2 \rfloor - 1$ 的是叶子

直觉：完全二叉树里，叶子大约占一半（底层最多），所以"前一半是内部节点、后一半是叶子"。

这个规则在建堆时会用到（8.3 节：从最后一个非叶节点开始往前下沉，正是从 $\lfloor n/2 \rfloor - 1$ 开始）。

11.1.3

• (a) 对。 数组顺序就是完全二叉树的层序遍历顺序 —— 从上到下、每层从左到右。

  这也解释了为什么"完全二叉树"是必需的：如果有空洞，层序编号和数组下标就不再一一对应了。

• (b) 错（说法有歧义）。 堆不是有序结构 —— 它的数组顺序没有任何全局有序性（实测 3 排在 5 后面）。

  准确的说法：堆是"部分有序"的 —— 只保证父子之间的偏序关系。

  它"能快速找到最值"不是因为它有序，而是因为堆序性质保证了"最值一定在根上"。

• (c) 错。 如第四节所述，数组实现是严格更优的：更省内存、缓存更友好、找父子是 $O(1)$ 计算。链表反而要为每个节点多存两个指针，还要额外维护父指针。

  "树 = 指针"这个印象来自 BST —— 因为 BST 需要在中途任意位置增删，无法用数组紧凑表示。堆没有这个需求，所以数组才是对的。

• (d) 错。 大顶堆只保证"父 ≥ 子"，不保证全局有序。

  反例：[9, 7, 8, 3, 5, 6] 是大顶堆，但 7 在 8 前面（$7 < 8$）。

  大顶堆的数组不是降序排列。只有反复"取根 + 下沉"（也就是堆排序）之后，才能得到有序序列。

11.1.4

(a) 用大顶堆。

因为"优先级最高的先执行" = 每次要取最大值 → 大顶堆的根就是最大值。

注意别搞混：这里"优先级高"对应"数值大"。如果业务里约定"数字越小优先级越高"（比如 Linux 的 nice 值），那就该用小顶堆。

关键是问清楚"哪个方向是'最优先'"，而不是机械地记"调度器用大顶堆"。

(b) 放在数组【末尾】，然后上浮（sift up）到正确位置。

不能直接插在中间 —— 那样会破坏"完全二叉树"的结构（中间出现空洞）。

(c) 取出根之后：

1. 把末尾元素移到根的位置（下标 0）
2. 删除末尾（数组长度减 1）
3. 对根执行下沉（sift down），恢复堆序

为什么是"把末尾移到根"而不是"直接删根"？

因为删掉根会在树的顶部留一个空洞，破坏"完全二叉树"的性质（完全二叉树要求节点靠左连续）。

把末尾元素填补到根上，既保持了"完全"（长度减一，形状仍然合法），又只需要一次下沉就能恢复堆序。

这正是 8.3 节堆排序里做的事 —— 那里是"把根和最末尾交换"，本质相同。

11.1.5

(a) 对下标 $i$ 的节点：

• 第 $k$ 个孩子（$k = 0, 1, \ldots, d-1$）：下标为 $d \times i + k + 1$
• 父节点：$\lfloor (i-1)/d \rfloor$

验证（$d = 3$）：下标 0 的孩子是 $1, 2, 3$ ✓；下标 1 的孩子是 $4, 5, 6$ ✓；下标 4 的父是 $\lfloor 3/3 \rfloor = 1$ ✓

(b) 高度 = $\log_d n$。

因为每个节点有 $d$ 个分支，从根往下每层节点数 × $d$，所以层数是 $\log_d n$。

(c) 好处和坏处：

具体来说：$d \log_d n$ 在 $d = e \approx 2.718$ 时最小。

所以在纯数学意义上，二叉堆（$d=2$）已经很接近最优了。

但实际中，4 叉堆（$d=4$）常被认为更好 —— 原因是缓存：

• 二叉堆的高度是 $\log_2 n$，$n = 10^6$ 时约 20 层
• 4 叉堆的高度是 $\log_4 n$，约 10 层

虽然每层多比较几个孩子，但层数少了近一半，而且前几层的数据整个都在缓存里 —— 实际运行更快。

这和 3.1 节的缓存效应、以及 6.2 节"开放寻址探测更多却更快"是同一个道理：

理论上的操作次数，不等于实际的运行时间。

八、常见错误

九、本节总结

1. 堆 = 完全二叉树 + 堆序性质。堆序只要求"父 ≤ 子"（小顶堆）或"父 ≥ 子"（大顶堆）。
2. 堆不是有序结构 —— 实测 [2,5,3,8,7,6] 里 3 排在 5 后面。它只是"部分有序"。
3. 这个"弱"约束正是堆的价值：维护全局有序要 $O(n \log n)$，维护堆序只要 $O(\log n)$。
4. 父子下标公式：左孩子 $2i+1$、右孩子 $2i+2$、父节点 $\lfloor (i-1)/2 \rfloor$。
5. 数组实现是严格更优的（不是"图省事"）：零指针开销、缓存友好、父子 $O(1)$ 计算。前提是完全二叉树 + 只在两端增删。
6. 判断叶子：下标 $> \lfloor n/2 \rfloor - 1$ 的就是叶子。建堆从这里开始（8.3 节）。
7. d 叉堆：$d=2$ 在数学上接近最优，但 $d=4$ 因为缓存效应常被认为更实用。

下一节衔接：堆的定义和表示讲完了，但怎么维持它？插入一个元素后，堆序可能被破坏；删掉根之后，堆序也会被破坏。修复这两种破坏需要两个方向相反的操作 —— 上浮和下沉。下一节把它们讲清楚。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "11.1",
  "title": "堆的定义与数组表示",
  "covered": [
    "「堆不是有序数组」的实测对比（2 5 3 8 7 6 vs 2 3 5 6 7 8）",
    "堆的两个条件：完全二叉树 + 堆序性质",
    "父子下标公式与逐项验证表格",
    "为什么数组实现是「严格更优」而非「图省事」",
    "大顶堆与小顶堆的用途区别",
    "判断叶子的规则（下标 > n/2-1）",
    "d 叉堆的分析与缓存效应"
  ],
  "unresolved": [
    "上浮与下沉留到 11.2",
    "堆的完整实现留到 11.3",
    "Top-K 与优先队列工程用法留到 11.4",
    "堆排序已在 8.3 节讲过"
  ],
  "canonical_terms": {
    "堆（Heap）": "完全二叉树，父节点不小于（或不大于）它的孩子",
    "堆序（Heap Property）": "父节点与孩子之间的大小约束",
    "小顶堆（Min-Heap）": "父节点不大于孩子的堆，根是最小值",
    "大顶堆（Max-Heap）": "父节点不小于孩子的堆，根是最大值"
  },
  "symbols_units": {
    "d": "d 叉堆的分支数"
  },
  "assumptions": [
    "读者已掌握 9.1 的树术语与 3.1 的连续内存",
    "读者已读过 8.3 节的堆排序（本节与其互补而非重复）"
  ],
  "word_count_actual": 2680,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch11/Sec111/",
    "树形打印、下标公式表、大顶堆验证、局部有序对比均为实测",
    "练习 11.1.1/11.1.2 的下标计算已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版 IsMinHeap 的 verbose 分支在插值字符串里写了 a[{right}]，触发 CS1003 语法错误（嵌套括号解析问题），且该分支实际未被调用；已改为字符串拼接并保留 verbose 能力"
  ],
  "next": "11.2 上浮与下沉"
}