堆与优先队列
01 / 共享的机制
堆让你廉价地拿到极值 —— 最小或最大 —— 而其余元素保持松散的、半排序状态。三个子模式:一个堆做 Top-K,两个堆维护流式中位数, 一个由源指针构成的小顶堆合并 K 路有序流。
01 / 一句话本质
要在 N 个元素中追踪最极端的 k 个,维护一个大小为 k 的堆, 其堆顶是这 k 个中最差的那个 —— 每个新元素要么把堆顶挤出去,要么不挤。
题目流中前 k 大数据流[3, 1, 5, 12, 2, 11, 7, 8]k3
数据流
30
11
52
123
24
115
76
87
—— 堆为空 ——
heap = [ ]
维护一个大小为 k = 3 的小顶堆。堆顶是前 k 大中最小的 —— 任何严格更大的新元素都会把堆顶挤出去。
步
0 / 17
堆大小
0
堆顶最小
—
动作
init
0 / 17
02 / 模式骨架
# 前 k 大 —— 大小为 k 的小顶堆heap ← [ ]for x in stream:if |heap| < k:heap.push(x)elif x > heap[0]:heap.replace_root(x)return sort(heap, descending)# 前 k 小:换成大顶堆,比较方向取反
03 / 什么时候用这个模式
"前 k / 第 k 大"
你要的是最极端的 k 个,而不是完整的排序。 重点是把开销压到
O(N log N) 之下。"流式 / 在线"
元素一个个到达,无法一次看全。大小为 k 的堆能在常数内存下给出答案, 无论数据流有多长。
"频次 / 加权"
“极端”指的不是原始值,而是某种派生键,如出现次数或距离。 算法相同,只是比较器变了。
"分位数 / 第 k 大"
滑动窗口或流式数据中的第 k 大,正好就是大小为 k 的堆自然维护的量。 若需要在线中位数,则需要两个堆 —— 见双堆。
04 / 常见坑
i.
用大顶堆找最大。
求前 k 大时应当使用大小为 k 的小顶堆 —— 堆顶是这 k 个中最小的, 更大的新元素会把它挤出去。大小为 k 的大顶堆会把目前见过的最大值放在顶端, 反而无法廉价地检查第 k 大。
ii.
替换时用严格
> 还是非严格 ≥。严格
> 下,等于堆顶的新元素会被拒绝 —— 已有的那一个保留。 而 ≥ 会把新值换进来。无重复输入时两者结果相同; 有重复时则会发生分歧。根据题目要求选择。iii.
排序就够用时硬上堆。
如果 N 个元素已全在内存中且 k 接近 N,直接排序更简单,性能也具竞争力。 堆真正胜出在 N ≫ k,或者数据是流式、无法一次性缓存的场景。
05 / 去 LeetCode 上练习
四道题。第一题是经典的“第 k 大”。第二题换用频次作为键 —— 算法相同,比较器不同。 第三题强化流式场景。第四题是把堆与贪心选择结合起来的经典应用。
— / 什么时候用哪个
Top-K
当你只要最极端的 k 个而不是完整顺序时使用。
流式 · O(N log k) · LC 215 / 347 / 703
双堆
当你要在线维护中位数时使用 —— 用大顶堆装下半,小顶堆装上半。
中位数 · 大顶堆 + 小顶堆 · LC 295
合并 K 路
当有 K 个有序流,需要不断取出当前最小值时使用。
合并 · (val, src, idx) · LC 23 / 378