堆与优先队列
01 / 共享的机制
堆让你廉价地拿到极值 —— 最小或最大 —— 而其余元素保持松散的、半排序状态。三个子模式:一个堆做 Top-K,两个堆维护流式中位数, 一个由源指针构成的小顶堆合并 K 路有序流。
01 / 一句话本质
要合并 K 个有序流,维护一个每个流贡献一个指针的小顶堆 —— 每次弹出就是所有流中下一个最小元素,每个元素的开销固定为 O(log K)。
题目合并 K 条有序列表K3列表L0=[1,4,7] L1=[2,5,9] L2=[3,6,8]
L0
1
4
7
L1
2
5
9
L2
3
6
8
堆(value, src, idx)
—— 空 ——
out
·
3 条有序列表。给一个小顶堆种子 —— 每条列表压入头部,堆中始终保留每个源的一个前沿。
步
0 / 22
|堆|
0
|out|
0
堆顶
—
0 / 22
02 / 模式骨架
# 把 K 路有序合并成一条有序输出heap ← min-heap[ ] # 键 = (value, src, idx)for s in 0..K−1:if lists[s] not empty:heap.push((lists[s][0], s, 0))while heap not empty:(val, s, i) ← heap.pop()out.append(val)if i + 1 < |lists[s]|:heap.push((lists[s][i+1], s, i + 1))# 元组顺序:相等时先按 src,再按 idx —— 稳定
03 / 什么时候用这个模式
"合并 K 个有序列表 / 文件"
最典型的信号。两两归并的总开销是
O(N · K); 堆始终保留 K 个开放指针,把它压到 O(N log K)。"外部排序"
先把能进内存的块排好序写出,然后用堆把这些块合并 —— 这正是数据库对超过 RAM 的表做排序的方式。
"在多个结构中找第 k 小"
有序矩阵中的第 k 小、两个有序数组的第 k 小和、第 k 小的对距离 —— 这些本质都是合并 K 路。
"覆盖所有列表的最小区间"
每个列表在堆中保留一个前沿元素;堆顶最小值与当前全局最大值之间的跨度, 就是一个候选区间。
04 / 常见坑
i.
一次性把整条列表压入堆。
关键在于堆始终保持 K 个元素,而不是 N。初始时每条列表只压入头部, 每次弹出后再推进相应的源指针。否则你只是绕了一圈做了个
O(N log N) 排序。ii.
忘了用元组 —— 键必须带上来源。
堆里存的是
(value, src, idx)。没有源指针就无法在弹出后推进正确的列表, 没有索引就无法取到下一个元素。两者都必须随值一起携带。iii.
遇到相等值就崩溃的比较器。
元组排序的堆必须给出相等时的次序 —— 通常按 src。某些库 (Python 的
heapq 对对象,Java 的 PriorityQueue<ListNode>)在第一项相等时会比较第二项; 要么保证第二项可比较,要么提供比较器。05 / 去 LeetCode 上练习
四道题。第一题是经典原型。中间两题是「换皮」的合并 K 路 —— 有序矩阵与两数和表。 最后一题是经典的「最小区间」变体。
— / 什么时候用哪个
Top-K
当你只要最极端的 k 个而不是完整顺序时使用。
流式 · O(N log k) · LC 215 / 347 / 703
双堆
当你要在线维护中位数时使用 —— 用大顶堆装下半,小顶堆装上半。
中位数 · 大顶堆 + 小顶堆 · LC 295
合并 K 路
当有 K 个有序流,需要不断取出当前最小值时使用。
合并 · (val, src, idx) · LC 23 / 378