Theory · Data Structure · Heap & Priority Queue
完全二叉树 + 堆序：建堆 O(n) · TopK · 双堆中位数 · container/heap —— "只要最值"场景的最优解
完全二叉树数组化：零指针开销，父子全靠下标公式
上浮/下沉 O(log n)，建堆却是 O(n)——本 deck 与复杂度 deck 的招牌联动
TopK 用反直觉的小顶堆、流式中位数用双堆——面试最高频的两套组合拳
Why It Matters
病人陆续到（随时插入），医生每次叫号要叫病情最重的那个（随时取最值）。普通队列只会按到达顺序发号——它管不了"优先级"。任务调度器、Dijkstra 找最近节点、限流的定时器，全是同一个需求。
插入 O(1) 很爽，但每次叫号要扫全部。100 万个待处理任务，就是 100 万次比较，而且每叫一次都要重来。
取最大变成 O(1)（拿第一个），但每插入一个都要挪数据 O(n)。把成本从"取"搬到了"插"，总账没变。
排序是把 n 个元素两两之间的关系全部确定下来——可我们每次只想知道一个：谁最大。用更弱的约束换更低的维护成本：只要求"每个父亲都不小于它的孩子"，那么根一定是全局最大，而兄弟之间乱着也没关系。这个"半有序"的结构就是堆。
| 做法 | 插入一个 | 取走最大 | 问题 |
|---|---|---|---|
| 无序数组 | O(1) | O(n) 扫全表 | 取太贵，100 万次比较 |
| 始终保持有序 | O(n) 挪数据 | O(1) | 插太贵 |
| 平衡树 | O(log n) | O(log n) | 能做，但维护了用不到的全序，还有指针开销 |
| 堆 | O(log n) | O(log n) | 零指针（住在数组里），但只能取最值 |
container/heap 怎么用不踩坑。
Prerequisites & Glossary
| 术语 | 一句话理解（细节后面展开） |
|---|---|
| 优先队列 priority queue | 一种需求：随时插入、每次取出优先级最高的；它不指定怎么实现 |
| 堆 heap | 实现上述需求最常用的结构；二者常被混着叫，但一个是需求一个是做法 |
| 完全二叉树 | 除最后一层外每层填满、最后一层靠左连续——正因如此才能塞进数组 |
| 堆序 heap order | 唯一的约束：每个父亲都不小于（或不大于）它的孩子；兄弟之间不作要求 |
| 大顶堆 / 小顶堆 | 根是最大值 / 根是最小值；两者只差一个比较符号方向 |
| 堆顶 peek | 数组第 0 个元素，就是当前最值；看一眼是 O(1) |
| 上浮 sift-up | 元素比父亲"更该在上面"，就和父亲交换，一路往上直到不再违规 |
| 下沉 sift-down | 元素比孩子"更该在下面"，就和更该上位的那个孩子交换，一路往下 |
| 建堆 heapify | 把一个乱序数组一次性整理成堆的过程（第 5 页会证明它是 O(n)） |
| 惰性删除 | 不真删，先留在堆里，等它浮到堆顶时再发现"已过期"并丢弃 |
二叉树 → 完全二叉树、树高、以及数组下标公式的来源
数组与链表 → 堆为什么住在数组里就赢了
复杂度分析 → "建堆 O(n)"那一步求和的读法
堆只保证一件事：根是全局最值。父子之间有序，兄弟之间完全无序。
所以它做不了"查找某个值""按范围取""排第几名"——那些要找平衡树。
把一个站错位置的元素沿着父子链一路交换到它该去的地方：往上换叫上浮，往下换叫下沉。父子链最长就是树高，所以每次操作最多 log n 步。
插入 = 放到数组末尾然后上浮；取走堆顶 = 把末尾元素搬到堆顶然后下沉。就这两招。
Complete Tree + Heap Order
把开场那个"半有序"的想法写成定义：形状上是完全二叉树（所以能住进数组），秩序上只要求父子有序。
Sift Up / Sift Down
// 小顶堆：上浮（新元素从尾部升起） func siftUp(a []int, i int) { for i > 0 { p := (i - 1) / 2 if a[p] <= a[i] { break } a[p], a[i] = a[i], a[p] i = p } } // 下沉（堆顶被换走后归位） func siftDown(a []int, i, n int) { for { l, r, m := 2*i+1, 2*i+2, i if l < n && a[l] < a[m] { m = l } if r < n && a[r] < a[m] { m = r } if m == i { return } a[i], a[m] = a[m], a[i] i = m } }
新元素放尾部（保持完全性），一路与父比较交换——最多走树高 O(log n)。
堆顶（a[0]）与尾元素交换、缩容量，再让新堆顶下沉归位——同样 O(log n)。用"换尾"而不是"挖洞"保持完全性，是数组化堆的精髓。
O(1)——这是堆存在的意义：最值永远在顶部等着。
push O(log n) · pop O(log n) · peek O(1) · 建堆 O(n)（下一页）· 任意查找 O(n)（兄弟无序）。
Build Heap · The Classic Trap
从空堆开始 n 次上浮，第 i 次最坏 O(log i)，总 O(n log n)。能对，但不是最优。
从最后一个非叶节点（⌊n/2⌋−1）倒着 siftDown。高度 h 的节点至多 n/2^(h+1) 个，每个代价 O(h)：
Σ (n/2^(h+1))·O(h) = O(n)·Σ h/2^h = O(n)·2 = O(n)
一半节点是叶子（代价 0），代价集中在稀疏的顶层——与 复杂度 deck 的主定理陷阱题完全同源。
手里已有一批数据要变成堆（堆排序第一步、初始化优先队列），永远用一次性建堆而不是循环 push——常数差一倍以上。
// 堆排序第一步：一次性建堆 O(n) func buildHeap(a []int) { // 最后一个非叶节点开始，倒着下沉 for i := len(a)/2 - 1; i >= 0; i-- { siftDown(a, i, len(a)) } } // 堆排序完整版：O(n log n)，O(1) 空间 func heapSort(a []int) { buildHeap(a) // O(n) for end := len(a) - 1; end > 0; end-- { a[0], a[end] = a[end], a[0] // 最值换到末尾 siftDown(a, 0, end) // O(log n) } }
TopK Pattern · LC 215/347
TopK · Three Solutions
| 方案 | 时间 | 空间 / 适用 |
|---|---|---|
| 全排序 | O(n log n) | O(1)~O(n)；数据全在内存、一次问 |
| 小顶堆 | O(n log k) | O(k)；流式/海量数据，k 远小于 n 时最优 |
| 快速选择 | 平均 O(n)，最坏 O(n²) | O(log n) 栈；只问一次且允许重排数组 |
先 map 统计频次 O(n)，再对（频次, 元素）对维护 k 大小顶堆（按频次比大小）O(n log k)。桶排序变体：频次作下标，O(n) 极限。
k 路归并：k 个链表头进小顶堆，每步弹最小接到结果、把它的 next 入堆——O(N log k)。这是"堆维护多个来源当前最优"的通用范式（后续 Dijkstra 同款）。
构造时建 k 小顶堆，之后每个 add 流式处理——TopK 的流式版，考的就是堆方案的天然在线性。
Two Heaps · LC 295
Go Stdlib · container/heap
// 实现五个方法即可获得堆能力 type IntHeap []int func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] // 大顶堆改 > } func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x any) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() any { old := *h; n := len(old) x := old[n-1] *h = old[:n-1] return x } // heap.Init(&h) / heap.Push(&h, v) // heap.Pop(&h) / heap.Fix(&h, i)
标准库只提供堆算法（上浮下沉逻辑），元素怎么比大小由你的 Less 决定——非侵入式接口，任何类型都能变堆。
① Push/Pop 必须定义在指针接收者上（要改长度）；② Pop 的实现自己负责弹出并返回（库只负责调整顺序，约定堆顶在末尾）；③ 元素被 heap.Remove/Fix 后下标失效，外部索引要自己维护。
元素优先级变化时（如任务改期），Fix(h, i) 在原地下沉/上浮 O(log n)——比"删了重插"干净，这就是索引堆的用法（Dijkstra 里 decrease-key 的 Go 实践）。
time.Timer 底层是四叉堆（4-ary）：比二叉堆浅一层、缓存更友好——runtime 热路径的真实取舍。
Where Heaps Live
① Dijkstra：每次取当前距离最小的节点 O(log V)（图 deck）；② 合并 k 路有序：23 题范式；③ Huffman 编码：每次取两个最小频率合并；④ 堆排序。
① 定时器/超时管理：到期时间建小顶堆，peek 最近到期事件（Go runtime 四叉堆、Kafka 延迟队列的时间轮+堆）；② 任务调度：优先级队列；③ 网络拥塞控制的事件队列。
热搜榜 TopK 实时更新、推荐候选截断（海量打分取前 k）、限流中的最贵请求识别——"流式 + 只要前 k"的统一答案。
| 场景 | 用什么堆 | 关键操作 |
|---|---|---|
| Dijkstra | 小顶（距离） | Pop 最小 + 惰性/定点更新 |
| 定时器 | 小顶（到期时间） | Peek + Fix（改期） |
| TopK 流式 | 小顶（门槛） | Push + 淘汰堆顶 |
| 中位数 | 大顶+小顶对峙 | 两堆搬运平衡 |
| k 路归并 | 小顶（k 个头） | Pop + Push(next) |
LeetCode Shortlist
| 分组 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| TopK 家族 | 215 数组第K大 M · 347 前K个高频 M · 703 数据流第K大 E · 973 最接近原点的K个点 M | 215 先堆后快选；347 堆+计数 |
| k 路归并 | 23 合并K个升序链表 H · 378 有序矩阵第K小 M · 632 最小区间 H | 23 是范式：堆维护 k 个"当前候选" |
| 双堆 | 295 数据流的中位数 H · 480 滑动窗口中位数 H · 502 IPO H | 295 是母题；480 加滑动窗口过期 |
| 模拟/贪心 | 1046 最后一块石头 E · 621 任务调度器 M · 1642 可达最多建筑 H | 1046 练手；621 堆+数学 |
Cheat Sheet
| 看最值 peek | O(1)——就是数组第 0 个 |
| 插入 push | O(log n)：追加到末尾 + 上浮 |
| 弹出最值 pop | O(log n)：末尾元素搬到堆顶 + 下沉 |
| 建堆 heapify | O(n)（自底向上逐个下沉）；逐个 push 是 O(n log n) |
| 查找任意元素 | O(n)——堆没有查找能力，兄弟之间无序 |
| 删除任意元素 / 改优先级 | O(log n)，但前提是已知它的下标（要额外维护 值→下标 的映射） |
| 堆排序 | O(n log n) 时间、O(1) 空间、不稳定 |
| 只要最值，反复取 | 用堆（调度、Dijkstra、合并 k 路、定时器） |
| 要查找 / 范围 / 排名 | 用 平衡树 或 跳表 |
| 要完整有序结果 | 直接排序，别用堆逐个 pop |
| k 接近 n | 不如整体排序（O(n log n) 常数更小） |
| 数据放不下内存 | 分片各求局部 TopK，再归并 k 路（多路堆） |
| TopK 最大的 k 个 | 维护容量 k 的小顶堆：新元素 > 堆顶就换掉堆顶。时间 O(n log k)、空间 O(k)。 口诀：求最大用小顶堆——堆顶是"守门员"，专门淘汰不够格的 |
| 流式中位数 | 大顶堆存较小一半 + 小顶堆存较大一半；每次插入先进一个堆再把堆顶让给另一个，维持两堆size 差 ≤ 1。中位数 = 堆顶（奇）或两堆顶均值（偶） |
| 遍历顺序 | 数组顺序不是有序，只保证根最值；打印堆数组别当排序结果 |
| 不稳定 | 相同优先级不保证先来先出；要稳定就把入队序号加进比较键 |
| 优先级变了 | 不能直接改字段，必须 heap.Fix(h, i)（否则堆序被破坏而无人知晓）；或走惰性删除：插新的、弹出时丢弃过期项 |
| Go 接口反直觉 | 自己写的 Push/Pop 只管切片尾部追加/摘除，调用时必须用包函数 heap.Push/heap.Pop，它们才做上浮下沉 |
Interview QA · Part 1
先盖住答案自己答一遍，再展开对照——想不起来比看得顺眼记得牢；答不出的翻回上一页速查表。
堆只保证父子偏序（兄弟无序），BST 是全序（中序有序）。只要最值 → 堆 O(log n) 且数组化更省；要查找任意元素/范围/前驱后继 → BST。
自底向下沉：高度 h 的节点 ≤ n/2^(h+1) 个，Σ n/2^(h+1)·O(h) = O(n)·Σh/2^h = O(2n)。一半节点是叶子零代价；"每层 O(n)×log n"是把节点代价当层代价的经典错误。
操作只动一条根叶路径：上浮/下沉最多走树高次交换。完全树保证高度 = ⌊log₂n⌋，形状即保证。
堆顶是准入门槛（k 个里最小的）：x 比门槛大才进来，顶掉的是最没资格的。堆只需 k 个元素 → O(n log k)、内存 O(k)、支持流式。求前 k 小对称地用大顶堆。
不变式：左堆（大顶）全 ≤ 右堆（小顶）全，长度差 ≤1。实现取巧：新元素总是先入左堆，再把左堆顶搬去右堆；若右堆过长再搬一个回来——两步通用，免分类讨论。
不稳定：相等元素次序依赖交换路径。需要稳定序时给元素配单调递增序号作第二关键字（Less 里先比优先级再比序号）。
同为 O(n log n) 但堆排跳跃访问（i 与 2i+1 距离越来越远，cache miss 多）且不稳定；快排顺序访问、分支可预测。堆排的优势只有 O(1) 空间 + 最坏 O(n log n) 有界。
d 叉堆树更矮（log_d n）但每层比较更多——cache line 装得下 4 个子节点时，减少的 miss 赢多出的比较。runtime 热路径上"内存访问次数"比"比较次数"更贵。
Interview QA · Part 2
同样先自答再对照。这一页的题要"结论 + 一句代价/边界"才完整——只答结论会被继续追问。
两条路：索引堆（hash 记元素→下标，定点 Fix 上浮下沉 O(log n)）；或惰性删除——插入新版本、弹出时跳过过期项（Dijkstra 常用，代价是堆可能变大）。
库只实现算法（siftUp/siftDown 的索引操作），数据进出由你的方法负责：Push 靠你 append、Pop 靠你弹出末尾。Less 反向就是大顶堆。这是 Go 非侵入式接口的典型应用。
每一步要"k 个链表当前头里的最小者"——正是堆的语义：Pop 最小 O(log k) + Push 该节点的 next。对比两两归并 O(N log k) 同级但常数大、串行；堆版天然适配流式。
贪心正确性依赖"每次取当前距离最小的已确定节点"：数组扫 O(V²)，堆 O((V+E)log V)。稀疏图差距巨大——堆是图算法的标配外设（图 deck）。
可以：删除时只打标不搬堆，Pop 到标记项跳过。适合删除频繁但可容忍堆膨胀的场景（滑动窗口中位数 480 的过期窗口元素）。定期重建可回收空间。
堆方案天然适配：只维护 k 个元素的堆，流式扫全量数据 O(n log k)、内存 O(k)；多机场景每台出 TopK 再合并（k 路归并）。这就是"堆 = 流式算法"的意义。
① 需要任意元素查找/有序遍历 → BST/跳表（堆找任意元素 O(n)）；② 只取一次最值且可重排 → 快速选择更省（平均 O(n)）；③ 元素很少（k<10）直接线性扫——别为 O(1) 引入 O(log n) 的复杂性。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch6 · Heapsort / Priority Queues | 堆性质、BUILD-MAX-HEAP 的 O(n) 分析、堆操作 |
| src/container/heap/heap.go | Interface 五方法约定、Init/Push/Pop/Fix/Remove 实现 |
| src/runtime/time.go（本机 Go 版本） | 定时器四叉堆（timers 4-ary heap）实现 |
| LeetCode 215/347/23/295 官方题解 | TopK 三方案、k 路归并、双堆模式 |
| oi-wiki.org/ds/binary-heap | 堆的中文系统讲解与 d 叉堆讨论 |