Data Structures
课程 · #7 / 11

堆与优先队列

数组支撑、对数时间取最小值——优先队列的引擎

Min-heap · array view ↔ tree view

array 
init

动手试试：插入元素，看 bubble-up（上浮）时成对交换的闪烁。然后 extractMin——下沉（sift-down）会重建不变式。同一个数组，两种看法：一行格子，和一棵完全二叉树。

为什么它重要

堆就是 二叉树那一课 里那棵数组支撑的树——只不过多加了一条规则，把它变成了一台常数时间取最小/最大值的引擎。当你需要快速、反复地取出最大（或最小）元素时，堆就是答案。它驱动着优先队列、堆排序，以及像 Dijkstra 最短路径（你在 图那一课的最短路径模式 里见过）这样的算法。

堆不变式

两条不变式，必须同时成立：

堆不变式
形状：这棵二叉树是完全的——除了最后一层之外每一层都填满，而最后一层从左到右依次填充。这让我们能把整棵树连续地存进一个数组，没有空洞。
顺序（小根堆）：对每个节点 n，对它的每个孩子都有 n.key ≤ key(child)。（改成 ≥ 就是大根堆。）因此根节点持有最小值（或最大值）。
"保住"意味着什么
插入会在叶子处临时破坏顺序，随后上浮将其重建。取出会临时同时破坏两者（最后一个叶子被搬到根），随后下沉在保持形状完全的同时重建顺序。

核心思想

想象一张淘汰赛对阵图，赢家总是往上升。每打完一场，更强的队伍就上移。

堆就是那个样子。 在大根堆里，每个父节点都大于它的孩子。根永远是最大值。

精妙的诀窍是：把它存进一个数组！对位于下标 i 的节点：

插入：在末尾添加，然后"上浮"——只要比父节点大就与父节点交换。 取出最大值：移除根，把最后一个元素放到根，然后"下沉"——只要比某个更大的孩子小，就与那个更大的孩子交换。

两个操作都是 O(log n)——正好是树的高度。

要点回顾

再深入一些

小根堆与大根堆

小根堆把最小元素放在根；大根堆把最大元素放在根。机制是完全一样的——只是比较方向翻转。有些语言默认是其中一种（C++ std::priority_queue 是大根堆；Python heapq 是小根堆），于是你通过取负来翻转——heapq.heappush(q, -value)。一定要先查清楚。

O(n) 建堆证明

你也许会以为，从 n 个无序元素建堆要花 O(n log n)——每个元素一次 O(log n) 的插入。但有更好的办法：拷贝数组，然后从中间下标开始朝根的方向逐个下沉。总代价是 O(n)，而非 O(n log n)。

证明是一个漂亮的几何级数求和。一棵有 n 个节点的完全二叉树大约有 n/2 个叶子（深度 0——无需下沉）、n/4 个在深度 1（每个至多 1 次交换）、n/8 个在深度 2（至多 2 次交换）……以及深度 log n 处的 1 个根（至多 log n 次交换）。总工作量：

work ≤ Σ (n / 2^(d+1)) · d   for d = 0..log n
     = (n/2) · Σ d / 2^d
     ≤ (n/2) · 2     since Σ d/2^d converges to 2
     = O(n)

绝大多数节点都靠近底部，只下沉零层或一层。只有顶部那微不足道的一小部分节点要做满 log n 的工作。这是摊还分析的又一种风味——最坏情况集中在少数几个节点上，而它们少到不足以主导全局。

堆与 BST —— 何时选哪个

两者都给你 O(log n) 的操作。决定用哪个的，是两个实际差异：

| 使用场景 | 堆 | BST | |---|---|---| | 反复取最小/最大值 | ✓ O(1) 查看，O(log n) 弹出 | 取最小/最大也是 O(log n) | | 范围查询（找出所有 > 50） | ✗ 无顺序 | ✓ O(log n + k) | | 中序遍历 | ✗ | ✓ | | 内存开销 | 数组——无指针 | 每个节点 2 个指针 + 值 | | 常数因子 | 小（数组，缓存友好） | 较大（指针追逐） | | 从 n 个元素构建 | O(n) 建堆 | O(n log n) 反复插入 |

当你只需要最小/最大值、从不需要顺序或范围查询时，选堆。当你需要有序迭代或"找出 [a, b] 区间内的所有键"时，选 BST（通常是平衡的）。图那一课的 Dijkstra 模式 用堆，是因为它始终只需要下一个代价最小的边界节点，而不是所有边界节点的顺序。

堆排序正是利用了这一点：用 O(n) 建堆，然后取出最大值 n 次，总体 O(n log n)——但它的缓存表现比 归并排序 更差，所以尽管渐近界相同，它在实践中很少胜出。

数学细节

时间复杂度
Insert: O(log n)
Extract max/min: O(log n)
Peek: O(1)
Heapify (build): O(n)
数组下标公式
left(i) = 2i + 1
right(i) = 2i + 2
parent(i) = lfloor(i-1)/2rfloor

实现

堆操作

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);  // Heap: max at top

let max = heap.pop();  // Returns Some(4)
let peek = heap.peek(); // Returns Some(&3)

何时使用

练习

三道题目，展示了为什么遇到"给我最好/最差的 k 个东西"时，堆是你的默认工具：

→ 浏览全部练习题