第 14 章堆 — 数组里的完全二叉树¶

这一章讲什么: 一种「住」在数组里的二叉树,两个性质(结构 + 堆) 换三个 O(log n) 内的操作;它是优先队列的标准实现,也是堆排序的引擎, 外加两个变体(d 叉堆、treap)。它在全书链条里的位置: 第 12 章树、第 10 章队列在此会师;第 17 章的 Dijkstra/Prim、第 15 章的高级堆都建立在本章的两个动作上——上浮与下沉。

1. 顶层全景¶

  堆 = 结构性质 + 堆性质
      │
      ├─ 结构性质:完全二叉树(叶全在最后一层且靠左)→ 可以用普通数组存,
      │            无需指针;父 = ⌊(i−1)/2⌋,左子 = 2i+1,右子 = 2i+2
      │
      ├─ 堆性质:父的键 ≥ 子的键(max heap;反转为 min heap)
      │            ⟹ 最大值必在根(top O(1))
      │
      ├─ 两个核心动作:
      │    add:尾插 → 上浮(比父大就交换,直到不比父大或到顶)O(log n)
      │    remove:顶出 → 尾元素补顶 → 下沉(与较大的孩子交换,直到比孩子都大或到底)
      │
      ├─ 应用一:优先队列(PQ)——先出优先级最高者
      │    候选实现对比:无序数组(top O(n))、有序数组(add O(n))、
      │    平衡树(全 O(log n))——堆全胜(全 O(log n) 且 top O(1),代码最短)
      │
      ├─ 应用二:堆排序——建堆(逐元素上浮,Williams)→ 顶尾交换收缩
      │    Floyd 改进:从 ⌊n/2⌋ 往下逐个下沉建堆,总 O(n)(大部分节点在底层)
      │    性质:最坏也 O(n log n)(比快排稳),但不稳定
      │
      └─ 变体:d 叉堆(上浮快、下沉慢;层数更少)、treap(键按 BST + 随机优先级按堆)

  图说:两个性质 → 两个动作 → 两个应用 → 两个变体,一章四个二。

2. 主线例子:add(56) 与 remove() 的完整走查¶

用原书图 14-5 的堆:数组 [60, 24, 34, 11, 9, 22, 12](60 是根)。

add(56)——三步上浮:

  ① 尾插:[60, 24, 34, 11, 9, 22, 12, 56](56 在位置 7)
  ② 56 的父 = ⌊(7−1)/2⌋ = 24;56 > 24,交换:[60, 24, 34, 56, 9, 22, 12, 11]
  ③ 56 的新父 = ⌊(3−1)/2⌋ = 60;56 < 60,停。

remove()——三步下沉:

  ① 顶出 60,尾元素 12 补顶,数组缩到 7:[12, 24, 34, 56, 9, 22, 11]
  ② 12 的孩子是 24(位置1)和 34(位置2),较大者 34;12 < 34,交换:
     [34, 24, 12, 56, 9, 22, 11]
  ③ 12 的新孩子在位置 5(22)、6(11),较大者 22;12 < 22,交换:
     [34, 24, 22, 56, 9, 12, 11]
  ④ 12 再无孩子(位置 5 起越界),停。remove 返回 [新堆, 60]。

代码骨架:add = push + _bubbleUp(尾);_bubbleUp(i) 与父比、交换、递归; remove 取顶、尾补、缩长、_sinkDown(0, 新长);_sinkDown 先算左右孩子, 与「三者最大者」比,换位递归²。两个动作都只走一条根到叶的路径, 故 O(log n);性能表:top O(1)、add/remove O(log n)³。

3. 核心原理¶

3.1 为什么数组能装树¶

完全二叉树的定义(第 12 章预告过):只有最后一层可能不满,且叶子全部靠左。这个形状有一个工程奇迹:给节点按层编号后,父子下标是纯算术关系 (父 ⌊(i−1)/2⌋、左子 2i+1、右子 2i+2)——数组直接当指针用, 零额外内存、缓存友好。这正是第 12 章「完全树」概念等的那一章¹。

3.2 优先队列:选实现的完整对账¶

优先队列与第 10 章队列的差别:先出的不是先来者,而是优先级最高者 (操作系统调度、离散事件模拟的时间戳、Dijkstra 的最近顶点、Prim 的最便宜连接、 Huffman 编码的最小概率合并——书里列了一串应用)⁴。四种候选实现的对比是本章最值钱的选型表⁵:

实现	top	add	remove
无序数组	O(n)	O(1)	O(n)
有序数组	O(1)	O(n)(二分定位 + 物理搬移)	O(1)
平衡 BST	O(log n)(加 max 指针可 O(1))	O(log n),略慢	O(log n)
堆	O(1)	O(log n)	O(log n)

堆以「最低复杂度拿全 O(log n)」胜出。要注意「优先级」方向有歧义 (priority 1 到底最高还是最低,书里专门吐槽英语), 实现侧就是 max heap 与 min heap 之别⁶。

3.3 堆排序:两次 O(n log n) 夹一个优化¶

Williams(1964)原版两步:逐个上浮建堆;然后从尾到头「顶尾交换、收缩堆界、下沉修复」——每步把当前最大值归位⁷。分析:n 次上浮各 O(log n)、n 次下沉各 O(log n),总 O(n log n); 且最坏情况也是 O(n log n)——没有快排的 O(n²) 死穴; 代价是不稳定⁸。 Floyd 的改进只动第一步:从最后一个内点 ⌊(n−1)/2⌋ 倒序下沉建堆—— 「大多数元素在底层,下沉比上浮快得多」,整体建堆降到 O(n) (数学略去);代码反而更短⁹。

3.4 两个变体:d 叉堆与 treap¶

d 叉堆:每个节点 d 个孩子(三叉、四叉……),数组公式相应改为父 ⌊(i−1)/d⌋、子 di+1…di+d。阶数不变(全操作仍 O(log n)), 但性格改变:上浮更快(树更扁)、下沉更慢(要选 d 个孩子里的最大)—— 插入多删除少的负载选大 d,反之小 d¹⁰。

treap(1989,tree + heap 的合体):每个键配一个随机优先级, 结构同时满足 BST(按键)与堆(按优先级)。直觉:按优先级降序插入键, 得到的恰好是堆形——所以随机优先级 ≈ 随机插入顺序 ≈ 期望 O(log n)。优先级也可以用哈希函数从键算出(确定性随机,便于测试)。增删靠旋转保持双性质;删除双子节点是第三种删法(呼应第 12 章的预告)¹¹。

4. 作者的判断与证据¶

堆是 PQ 实现的优胜者有完整对账表支撑(四种实现三操作对比), 胜出理由明确:「全 O(log n) 外加 top O(1),复杂度最低」⁵。
堆排序的卖点是确定性:最坏 = 平均 = O(n log n), 与快排的对照(快排常数小但最坏 O(n²))明说;不稳定性也如实交代⁸。
Floyd 建堆 O(n) 给了直觉版证明:「大多数元素在底层」—— 完整数学略去,但与第 4 章「摊还」精神同源⁹。
treap 的随机性来源给了工程替代:哈希当「确定性随机」, 「分析依赖真随机,哈希生成的随机性也 work」——诚实的理论-工程差距声明¹¹。

判断(我们的,不是书里的): 本章最深刻的伏笔是第 15 章的引子: 数组堆的 remove 只能删堆顶,没法「删除或降低任意元素」—— 而 Dijkstra 恰好需要降键。第 15 章整个二项/斐波那契堆家族都是「给堆装上地址能力(指针化)+ 懒合并」的漫长答案。读本章时带着「数组表示牺牲了什么」这个问题,第 15 章的每一步动机就顺理成章。 如果错,会错在: 「Dijkstra 需要降键」确实是第 15 章各节的显式动机, 但「数组 vs 指针」的二分在 d 叉堆和 treap 处已被打破 (treap 本来就是指针结构)——把动机压缩成一句话会漏掉「合并操作」这个同样重要的驱动(二项堆的存在理由是 O(log n) 合并)。

5. 边界与局限¶

堆的查找/任意删除是 O(n):堆不是查找结构(习题 14.6/14.7 专门点破: 堆里随便找个值得线性扫;「中堆删除」虽可用下沉上浮修复但先要找到它);
不稳定:堆排序的不稳定性有专门习题(14.12);
d 叉堆的最优 d 没有定论:只给了「上浮快下沉慢」的性格描述;
treap 的期望平衡依赖随机性质量,哈希版便于测试但理论分析按真随机算。

6. 可带走的¶

堆两性质:完全(数组装得下)+ 父大子小;数组下标即指针:父 ⌊(i−1)/2⌋、子 2i+1/2i+2。
两动作:add 尾插上浮;remove 尾补顶下沉;各 O(log n),top O(1)。
PQ 选型:堆全胜(对照无序数组/有序数组/平衡树三操作表)。
堆排序:建堆 + 顶尾交换收缩;最坏也 O(n log n),不稳定。
Floyd 建堆:倒序下沉,O(n)——多数元素在底层,下沉比上浮快。
d 叉堆:上浮快、下沉慢;插入密集选大 d。
treap:键走 BST、随机优先级走堆;平衡靠概率;优先级可用哈希代随机。

7. 原文地图¶

主题	原书章	原文位置
结构性质与数组公式	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:37`(搜「located on the left」)
堆性质与 min/max	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:72`(搜「greater than or equal」)
add 上浮走查	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:258`(搜「56」) · `text/43-fm-priority-queues-and-heaps.txt:300`(搜「_bubbleUp」)
remove 下沉走查	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:338`(搜「sifting」) · `text/43-fm-priority-queues-and-heaps.txt:361`(搜「_sinkDown」)
堆性能表	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:406`(搜「Table 14-2」)
PQ 应用与方向歧义	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:496`(搜「schedulers」) · `text/43-fm-priority-queues-and-heaps.txt:493`(搜「problem with the English」)
四实现对账	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:588`(搜「unordered array」)
堆排序两版与 Floyd	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:631`(搜「heapsort_original」) · `text/43-fm-priority-queues-and-heaps.txt:675`(搜「guaranteed」) · `text/43-fm-priority-queues-and-heaps.txt:697`(搜「heapsort_enhanced」)
d 叉堆	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:1100`(搜「d-ary」) · `text/43-fm-priority-queues-and-heaps.txt:1149`(搜「bubbling up becomes faster」)
treap	Priority Queues and Heaps	`text/43-fm-priority-queues-and-heaps.txt:767`(搜「portmanteau」) · `text/43-fm-priority-queues-and-heaps.txt:770`(搜「decreasing order」)

出处:「Priority Queues and Heaps」第 34–45 段(text/43-fm-priority-queues-and-heaps.txt:37,搜「located on the left」)。原文:结构性质要求完全且叶靠左;由此得数组下标公式(父 ⌊(i−1)/2⌋、左右子 2i+1/2i+2)。 ↩
出处:「Priority Queues and Heaps」第 289–391 段(text/43-fm-priority-queues-and-heaps.txt:300,搜「_bubbleUp」;:361,搜「_sinkDown」)。原文:add 尾插后上浮;remove 取顶、尾补、缩长、下沉;代码逐行走查见第 258–355 段。 ↩
出处:「Priority Queues and Heaps」第 406–480 段(text/43-fm-priority-queues-and-heaps.txt:406,搜「Table 14-2」)。原文:top O(1)、add O(log n)、remove O(log n)。 ↩
出处:「Priority Queues and Heaps」第 485–496 段(text/43-fm-priority-queues-and-heaps.txt:496,搜「schedulers」)。原文:OS 调度、离散事件模拟、Dijkstra、Prim、Huffman 编码都依赖优先队列。 ↩
出处:「Priority Queues and Heaps」第 584–601 段(text/43-fm-priority-queues-and-heaps.txt:588,搜「unordered array」)。原文四种实现对账;「堆是实现 PQ 的最佳方式之一,复杂度加分」见第 601 段。 ↩↩
出处:「Priority Queues and Heaps」第 493 段(text/43-fm-priority-queues-and-heaps.txt:493,搜「problem with the English」)。原文注:priority 1 到底最高还是最低无定论,各软件约定不同;需要 min heap 见习题 14.4。 ↩
出处:「Priority Queues and Heaps」第 611–662 段(text/43-fm-priority-queues-and-heaps.txt:631,搜「heapsort_original」)。原文:逐元素上浮建堆,然后顶尾交换、下沉、堆界收缩;走查见第 646–662 段。 ↩
出处:「Priority Queues and Heaps」第 672–678 段(text/43-fm-priority-queues-and-heaps.txt:675,搜「guaranteed」)。原文:O(n log n) 且「任何数据都不会导致更坏情况,不像快排可能 O(n²)」;「堆排序不稳定」见第 678 段。 ↩↩
出处:「Priority Queues and Heaps」第 685–752 段(text/43-fm-priority-queues-and-heaps.txt:697,搜「heapsort_enhanced」)。原文:Floyd 改进把建堆降到 O(n),「大多数元素在底层,下沉比上浮快得多,数学从略」;倒序从 ⌊(n−1)/2⌋ 起逐个下沉。 ↩↩
出处:「Priority Queues and Heaps」第 1100–1149 段(text/43-fm-priority-queues-and-heaps.txt:1100,搜「d-ary」;:1149,搜「bubbling up becomes faster」)。原文:d 叉堆层数更少;「上浮变快(树更扁),下沉变慢(要在更多孩子里找最大)」。 ↩
出处:「Priority Queues and Heaps」第 764–770 段(text/43-fm-priority-queues-and-heaps.txt:767,搜「portmanteau」)。原文:treap 为 tree+heap 合成词;键按 BST、随机优先级按堆;「按优先级降序插入恰好满足堆性质,随机优先级 ≈ 随机插入顺序」;哈希可代随机数(确定性,便于测试)见第 767 段。 ↩↩

第 14 章 堆 — 数组里的完全二叉树¶