堆与优先队列
01 / 共享的机制
堆让你廉价地拿到极值 —— 最小或最大 —— 而其余元素保持松散的、半排序状态。三个子模式:一个堆做 Top-K,两个堆维护流式中位数, 一个由源指针构成的小顶堆合并 K 路有序流。
01 / 一句话本质
把数据流一分为二:大顶堆装下半,小顶堆装上半。让两堆大小始终平衡,中位数永远在某个堆顶。
题目数据流的在线中位数数据流[5, 2, 8, 1, 9, 3, 7]
数据流
50
21
82
13
94
35
76
low —— 大顶堆
—— 空 ——
low = [ ]
high —— 小顶堆
—— 空 ——
high = [ ]
中位数—
两个堆:左边是装下半的大顶堆,右边是装上半的小顶堆。中位数就在分界处。
步
0 / 28
|low|
0
|high|
0
中位数
—
0 / 28
02 / 模式骨架
# 双堆 —— low 大顶堆,high 小顶堆low、high ← max-heap[ ]、min-heap[ ]for x in stream:if low.empty() or x ≤ low.top():low.push(x)else: high.push(x)# 再平衡,使 |low| − |high| ∈ {0, 1}if |low| > |high| + 1: high.push(low.pop())elif |high| > |low|: low.push(high.pop())median ← |low| > |high| ? low.top() : (low.top() + high.top()) / 2
03 / 什么时候用这个模式
"在线中位数 / 流式"
最典型的信号。数字一个个到达,每次插入后都要给出当前的中位数。 每次都重新排序是 O(N),双堆把它压到 O(log N)。
"滑动窗口中位数"
同一套机制,加上对离开窗口元素的延迟删除 —— 通常用一张 “待删除” 哈希表,在每次访问堆顶时清理。
"上下两半的分界"
凡是答案由小于 x 与大于 x 两部分的分界决定的问题 —— 调度医生、平衡负载、 两个有序数组的中位数 —— 都可以用双堆思路看。
"下半部分的和 / 均值"
大顶堆本身就是一个有用对象:它的大小和元素之和,直接给出最小 k 个的均值,免费送。
04 / 常见坑
i.
每次插入后忘记再平衡。
大小不变式
|low| − |high| ∈ {0, 1} 只有立刻修复才成立。 少做一次再平衡,后续所有中位数的取值都会从错误的堆里读出来。ii.
根据大小而不是值来决定插入哪个堆。
与当前下半最大值比较,才是维持划分有序的关键。 盲目插入更小的那个堆,会破坏
max(low) ≤ min(high) 不变式,中位数就错了。iii.
偶数大小时中位数的溢出 / 偏差。
两堆大小相等时中位数为
(low.top() + high.top()) / 2。 在整数类型中和可能溢出;用更宽的类型计算 (或者 low.top() + (high.top() − low.top()) / 2 加上奇偶修正)。05 / 去 LeetCode 上练习
四道题。第一题是经典原型。中间两题加入滑动窗口与滑动平均。 最后一题是表面无关、内核是双堆思路的经典题。
— / 什么时候用哪个
Top-K
当你只要最极端的 k 个而不是完整顺序时使用。
流式 · O(N log k) · LC 215 / 347 / 703
双堆
当你要在线维护中位数时使用 —— 用大顶堆装下半,小顶堆装上半。
中位数 · 大顶堆 + 小顶堆 · LC 295
合并 K 路
当有 K 个有序流,需要不断取出当前最小值时使用。
合并 · (val, src, idx) · LC 23 / 378