适用读者：会用
PriorityQueue但说不清"为什么建堆是 O(n)"的人。
前置：S03-B02。
实测环境：Python 3.12.3（heapq，即二叉堆实现）；实测日期 2026-11-05。
覆盖旧文：A-1503（堆，436 点）。
覆盖扩展：E-S03-009（定时器/合并 K 流）。
上一篇：S03-B04 · 哈希表与布隆过滤器：O(1) 的代价
下一篇：S03-B06 · 树家族。
1. 一句话结论
堆只维护一个弱条件——"父不小于子"（大顶堆）——就足以在 O(1) 取到极值、O(log n) 插入删除。它不保证整体有序，所以比排序便宜。
| 操作 | 有序数组 | 二叉堆 |
|---|---|---|
| 取最大值 | O(1) | O(1) |
| 插入 | O(n)（搬移） | O(log n) |
| 删除最大值 | O(n) | O(log n) |
| 建堆（n 个元素） | O(n log n)（排序） | O(n) |
| 全有序遍历 | ✅ | ❌ |
2. 实测：建堆为什么是 O(n)
20 万个随机整数：
| 方式 | 耗时 | 说明 |
|---|---|---|
heapify（自底向上调整） |
23.2 ms | O(n) |
逐个 heappush |
68.2 ms | O(n log n) |
比值 2.9×，与 log₂(200,000) ≈ 17.6 的理论比值不同——因为常数因子（列表构造、比较开销）占了大头。但方向明确：批量建堆更快。
2.1 为什么 heapify 是 O(n)
直觉版证明：自底向上调整时，大多数节点在底层（约 n/2 个叶子，调整 0 次；n/4 个节点调整 1 次……）。
总代价 = Σ (n / 2^(h+1)) × h ← 收敛到 2n = O(n)
对比"逐个插入"：每个元素从堆底 sift-up 到顶，平均 O(log n)。
3. 实测：Top-K 比全排序快多少
从 20 万个数里取前 10：
| 方式 | 耗时 |
|---|---|
heapq.nlargest(10, data)（维护大小 10 的堆） |
7.26 ms |
sorted(data, reverse=True)[:10]（全排序） |
109.02 ms |
15 倍差距。原理：堆只维护 K 个元素（O(n log k)），全排序要 O(n log n)。
判据：K 远小于 n 时用堆；K 接近 n 时排序更简单（常数更小）。
4. 堆的两种方向与实现要点
| 类型 | 堆顶 | 用途 |
|---|---|---|
| 大顶堆 | 最大值 | Top-K 最大、优先取大 |
| 小顶堆 | 最小值 | Top-K 最小、合并有序流、Dijkstra |
| 双堆 | 中位数 | 一个大顶堆（左半）+ 一个小顶堆（右半） |
4.1 数组存堆的两个公式（0 基）
父 → 子：left = 2i + 1, right = 2i + 2
子 → 父：parent = (i - 1) / 2
不需要真的建树——数组下标就是隐式的父子关系，这是堆"省内存"的关键。
4.2 sift-up 与 sift-down
| 操作 | 方向 | 复杂度 |
|---|---|---|
| 插入 | sift-up（向上比较交换） | O(log n) |
| 删除堆顶 | 末尾元素移到顶 → sift-down | O(log n) |
| 建堆 | 从最后一个非叶节点向前 sift-down | O(n) |
5. 工程里的堆（E-S03-009）
| 场景 | 用法 |
|---|---|
| 定时器/延时任务 | 小顶堆按"到期时间"排序，堆顶就是下一个要执行的任务 |
| 合并 K 个有序流 | 每个流取一个进堆，弹出最小的再补下一个（O(n log K)） |
| Top-K 热搜 | 维护 K 个计数的最小堆 |
| Dijkstra 最短路 | 优先队列取当前最短距离节点 |
| 中位数流 | 双堆（大顶 + 小顶） |
注意：Java 的 PriorityQueue 默认是小顶堆；要大顶堆需传 Comparator.reverseOrder()。
6. 五个误区
| 误区 | 真相 |
|---|---|
| "建堆是 O(n log n)" | heapify 是 O(n)（§2.1 证明） |
| "堆是有序的" | 只保证父子关系，兄弟无序 |
| "堆能快速查找任意元素" | 不能；查找是 O(n) |
"PriorityQueue 默认大顶堆" |
Java 默认小顶堆 |
| "Top-K 一定用堆" | K 接近 n 时排序更快（常数小） |
7. 自检
- 证明 heapify 为什么是 O(n)（用"底层节点多"的思路）。
- 20 万数据取 Top-10，堆与排序的实测耗时各是多少？
- 用数组存堆时，父子的下标关系是什么？
- 定时器为什么适合用小顶堆？
- 中位数流为什么需要两个堆？
8. 下一篇
S03-B06 · 树家族：BST → AVL → 红黑 → Trie
堆是"弱有序"的极致。下一篇看"强有序"的结构：BST 为什么退化、AVL 用什么换严格平衡、红黑树在折中什么，以及 Trie 为什么适合前缀搜索。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1503；扩展点 E-S03-009。heapify 23.2 ms / heappush 68.2 ms、Top-10 7.26 ms vs 109.02 ms 为 2026-11-05 实测。