⛰️ 01-数据结构与算法 · 主题 11:堆与 Top-K¶
堆是「动态取最大/最小」与「Top-K / 流式中位数」的利器,Python 用
heapq一行上手。 本 notebook 目标:吃透堆的性质与 heapq → 背熟 Top-K 模板 → 吃透 5 道高频题 → 通过 25 道自测。
前置:主题 3(链表)、主题 4(栈队列)。运行环境:Python 3.8+(heapq/collections)。
核心概念¶
(a) 🗂️ 堆与 Top-K:堆性质、手写二叉堆与流式模板¶
堆是"动态取最大/最小"与"Top-K/流式中位数"的利器,Python 用 heapq 一行上手。本 notebook 吃透堆的性质,背熟 Top-K 模板,并手写二叉堆。
flowchart TB
N1["⛰️ 堆的性质与 heapq"] --> N2["手写二叉堆:上浮 + 下沉"]
N1 --> N3["Top-K 模板:215 / 347"]
N3 --> N4["数据流第 K 大:703"]
N3 --> N5["双堆求中位数:295"]
N3 --> N6["合并 K 个有序链表:23"]
N2 --> N7["堆排序:了解 + 手撕备选"]
N7 --> N8["常见坑与边界"]
N8 --> N9["面试追问:为什么用小顶堆 / 建堆 O(n)"]
- N1 · 堆的性质与 heapq:堆是一棵"父节点总是最大/最小"的完全二叉树:取最值 O(1)、插入/删除 O(log n)。Python 的 heapq 默认小顶堆,基于 list 操作,一行上手。
- N2 · 手写二叉堆:数组存树 + 上浮(sift up)+ 下沉(sift down)两个函数:插入和删除堆顶都靠它们维护堆性质,是面试手撕加分项。
- N3 · Top-K 模板:一句话:用大小为 k 的小顶堆,新元素比堆顶大就替换。第 K 大(215)和前 K 高频(347,配哈希计数)都是它。
- N4 · 数据流第 K 大 703:维护大小为 k 的小顶堆,每来一个数 push + pop,堆顶永远是第 K 大——流式处理的标准做法。
- N5 · 双堆求中位数 295:大顶堆存较小一半 + 小顶堆存较大一半,两个堆大小差不超过 1,中位数就是堆顶之一。
- N6 · 合并 K 个有序链表 23:把所有头节点放进堆,每次弹出最小的,再把它下一个节点入堆——O(n log k),比两两合并快一个量级。
- N7 · 堆排序:先建堆再不断弹堆顶放进末尾:原地、O(n log n)、不稳定,可作为手撕备选,理解"建堆 O(n) + 弹 n 次 O(log n)"就够。
- N8 · 常见坑与边界:heapq 只有小顶堆(大顶堆要取负)、忘了维护堆大小、入堆元素类型搞混、数据流中两个堆平衡没调好。
- N9 · 面试追问:为什么 Top-K 用 k 大小的小顶堆(留守门员淘汰小的)、为什么建堆是 O(n)(从最后父节点开始下沉)、流式 Top-K/中位数的工程意义。
直觉类比 · 淘汰赛:堆就像体育淘汰赛——每轮只需和当前「最强候选」比一次(父子节点比较),$\log n$ 轮内就能确定冠军,不必与全员比较。 Top-K · 守门员:Top-K 的小顶堆 = 只留一个「守门员」(堆顶 = 第 K 大);新选手先跟守门员比,赢过守门员才换人进场,否则直接淘汰——门将永远保持第 K 大。
§1 堆的性质与 heapq¶
二叉堆 = 完全二叉树 + 堆序性质:
- 小顶堆:$parent \le children$(堆顶最小)
- 大顶堆:$parent \ge children$(堆顶最大)
Python 的 heapq 默认小顶堆;要大顶堆就把值取负存进去。
import heapq
hp = []
heapq.heappush(hp, 3) # O(log n)
heapq.heappop(hp) # O(log n) 弹出最小
hp[0] # O(1) 查看最小
heapq.heapify(arr) # O(n) 原地建堆
heapq.nlargest(k, it) # 便捷版
复杂度表(背熟)¶
| 操作 | 复杂度 |
|---|---|
| 查看堆顶 | $O(1)$ |
| 插入 / 删除堆顶 | $O(\log n)$ |
| 建堆 heapify | $O(n)$(不是 $O(n \log n)$!) |
| n 次插入 | $O(n \log n)$ |
为什么 heapify 是 $O(n)$:从最后一个非叶节点自底向上下沉,第 $h$ 层 $n/2^{h+1}$ 个节点各做 $O(h)$ 下沉:
$$\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot O(h) = O(n)$$
✍️ §1.1 手算建堆与 Top-2:[4,10,3,5,1] 的二叉堆¶
建堆:从最后一个非叶节点自底向上
sift-down——5 个元素手算,再把 Top-K 变一手。
设定:数组 [4,10,3,5,1](0-index 完全二叉树,$i$ 的左孩子 $2i+1$)。
第 1 步:定位非叶节点——下标 len//2 - 1 = 1(值 10)起:
- $i=1$(10):孩子 5、1 都小,不动
- $i=0$(4):左孩子 10 > 4 → 交换 →
[10,4,3,5,1];4 再与 5 交换 →[10,5,3,4,1]
第 2 步:堆序性质——堆顶 = 最大值 10;此时 Top-2 即再取一次堆顶后的次大值 5。
第 3 步:结论——Top-2 = [10, 5],完整排序对比 sorted = [1,3,4,5,10]。
手算收获:
- 建堆 $O(n)$ 的直觉:越靠下节点越多但下沉深度越浅——总工作量 $\sum n/2^i \times i = O(n)$,不是 $O(n\log n)$(§8.1 追问)
sift-down只与孩子比较:每次下沉高度 $\le\log n$,提取堆顶 $O(\log n)$,Top-K 用大小为 K 的小顶堆只需 $O(n\log K)$(§3 模板)- 面试手撕:heapq 只有小顶堆,大顶堆用负数入堆(§7 常见 bug)
- 堆排序 = 建堆 + 反复取堆顶放末尾:原地 $O(n\log n)$、不稳定(§6 堆排序)
下面 numpy 复算。
# ---- §1.1 验证:numpy 复算建堆与 Top-2 ----
import heapq
a = [4, 10, 3, 5, 1]
def siftdown(a, i, n):
while True:
largest = i
for ci in (2 * i + 1, 2 * i + 2):
if ci < n and a[ci] > a[largest]:
largest = ci
if largest == i:
break
a[i], a[largest] = a[largest], a[i]
i = largest
for i in range(len(a) // 2 - 1, -1, -1):
siftdown(a, i, len(a))
print(f'建堆后 = {a}(堆顶 {a[0]})')
assert a == [10, 5, 3, 4, 1]
h = [-x for x in [4, 10, 3, 5, 1]]
heapq.heapify(h)
top2 = [-heapq.heappop(h), -heapq.heappop(h)]
print(f'Top-2 = {top2}')
assert top2 == [10, 5]
print('\n✓ 与手算一致')
§2 手写二叉堆(面试加分)¶
堆用数组存完全二叉树:下标 $i$ 的左孩子 $2i+1$、右孩子 $2i+2$、父节点 $\lfloor (i-1)/2 \rfloor$。
两个核心操作:
- 上浮(sift up):插入末尾后与父节点比较交换,直到堆序恢复
- 下沉(sift down):删堆顶后把末尾移到堆顶,与较小孩子交换
class MinHeap:
def __init__(self): self.a = []
def push(self, x):
self.a.append(x)
self._sift_up(len(self.a) - 1)
def pop(self):
top = self.a[0]
self.a[0] = self.a[-1]
self.a.pop()
self._sift_down(0)
return top
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ============== 手写小顶堆 MinHeap(上浮 + 下沉) ==============
# 【题目目标】不依赖 heapq 手写小顶堆:支持 push(插入)与 pop(弹出最小值),
# 并验证全部弹出后得到升序序列(等价于堆排序)
# 【算法思路】用数组存完全二叉树:下标 i 的左孩子 2i+1、右孩子 2i+2、父节点
# (i-1)//2;上浮(_sift_up):push 时把新元素放数组末尾,与父节点反复
# 比较交换,直到恢复堆序(父 ≤ 子);下沉(_sift_down):pop 时把末尾
# 元素搬到堆顶,与较小的孩子反复交换直到堆序恢复
# 【变量含义】a:存储堆元素的数组;i:当前节点下标;p:父节点下标;l/r:左右
# 孩子下标;smallest:i 与其两个孩子中最小的下标;n:当前堆大小
# 【循环不变量】任意时刻数组都满足小顶堆性质 parent ≤ children,a[0] 恒为最小值
# 【递归终止】上浮:i==0(到根)或父 ≤ 子时停止;下沉:smallest==i(两个孩子都
# 不小于 i)时停止
# 【关键边界】下沉时访问 l/r 前先判 l<n、r<n(孩子越界);pop 取末尾后若堆非空
# 才把末尾搬到堆顶再下沉(堆空时直接返回);交换后 i 必须更新为
# smallest 继续下沉,否则死循环
# 【复杂度】push/pop 均 O(log n);全部弹出即堆排序 O(n log n)
# 手写小顶堆:用数组存完全二叉树,下标 i 的左孩子 2i+1、右孩子 2i+2、父节点 (i-1)//2
# 核心操作:上浮(插入后维护堆序)+ 下沉(删除堆顶后维护堆序)
class MinHeap:
def __init__(self):
self.a = [] # 用列表存储堆元素(完全二叉树)
def _sift_up(self, i):
while i > 0: # 还没到根就继续
p = (i - 1) // 2 # 父节点下标
if self.a[p] <= self.a[i]: # 父节点已不大于当前值 → 堆序满足
break # 停止上浮
self.a[p], self.a[i] = self.a[i], self.a[p] # 父子交换(小的往上走)
i = p # 继续从父节点位置向上
def _sift_down(self, i):
n = len(self.a) # 堆大小
while True:
l, r = 2 * i + 1, 2 * i + 2 # 左、右孩子下标
smallest = i # 假设 i 是最小的
if l < n and self.a[l] < self.a[smallest]: # 左孩子更小
smallest = l # 更新最小位置
if r < n and self.a[r] < self.a[smallest]: # 右孩子更小
smallest = r # 更新最小位置
if smallest == i: # 两个孩子都不比 i 小 → 堆序满足
break # 停止下沉
self.a[i], self.a[smallest] = self.a[smallest], self.a[i] # 与较小孩子交换
i = smallest # 继续下沉到交换后的位置
def push(self, x):
self.a.append(x) # 新元素放末尾
self._sift_up(len(self.a) - 1) # 从末尾上浮,恢复堆序
def pop(self):
top = self.a[0] # 堆顶就是最小值
last = self.a.pop() # 取出末尾元素
if self.a: # 堆里还有元素
self.a[0] = last # 末尾元素搬到堆顶
self._sift_down(0) # 从堆顶下沉,恢复堆序
return top # 返回最小值
# 测试:依次插入后全部弹出,弹出的顺序应是升序(即堆排序)
h = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
h.push(x) # 逐个入堆
out = []
while h.a: # 堆非空就弹出
out.append(h.pop()) # 每次弹最小值
print('手写小顶堆弹出顺序:', out) # 期望 [1, 2, 3, 5, 8, 9](升序 = 堆排序)
print('复杂度:push/pop 均 O(log n),等价堆排序 O(n log n)')
手写小顶堆弹出顺序: [1, 2, 3, 5, 8, 9] 复杂度:push/pop 均 O(log n),等价堆排序 O(n log n)
# ============== 手写大顶堆 MaxHeap(比较符号翻转版) ==============
# 【题目目标】手写大顶堆 MaxHeap:与 MinHeap 结构完全相同,仅把比较符号翻转
# (父节 ≥ 子节),支持 push / pop / peek,验证弹出为降序
# 【算法思路】上浮:新元素与父比较,父 < 子就交换(大的往上走);下沉:与较大的
# 孩子交换;peek 直接返回堆顶(不删除);逻辑与 MinHeap 一一对应
# 【变量含义】a:存储数组;i:当前下标;p:父节点;l/r:左右孩子下标;
# largest:i 与两个孩子中最大的下标;n:堆大小
# 【循环不变量】任意时刻满足大顶堆性质 parent ≥ children,a[0] 恒为最大值
# 【递归终止】上浮到父 ≥ 子或到根;下沉到 largest==i(孩子都不大于 i)停止
# 【关键边界】比较方向与 MinHeap 完全相反(> 换 <、l<r 换 l>r);pop 空堆特判;
# peek 不修改堆;交换后 i 更新为 largest
# 【复杂度】push/pop/peek 均 O(1)/O(log n);本次测试断言弹出顺序 == 降序,用于
# 交叉验证正确性
# 手写大顶堆:与 MinHeap 结构完全相同,只是把比较符号反过来(父节点 >= 子节点)
class MaxHeap:
"""大顶堆:与 MinHeap 结构相同,仅把比较符号翻转(parent >= children)。"""
def __init__(self):
self.a = [] # 存储堆元素的数组
def _sift_up(self, i):
while i > 0: # 还没到根就继续
p = (i - 1) // 2 # 父节点下标
if self.a[p] >= self.a[i]: # 父 >= 子:堆序已满足
break # 停止上浮
self.a[p], self.a[i] = self.a[i], self.a[p] # 父子交换(大的往上走)
i = p # 继续上移
def _sift_down(self, i):
n = len(self.a) # 堆大小
while True:
l, r = 2 * i + 1, 2 * i + 2 # 左、右孩子下标
largest = i # 假设 i 是最大的
if l < n and self.a[l] > self.a[largest]: # 找更大的孩子
largest = l # 左孩子更大
if r < n and self.a[r] > self.a[largest]: # 右孩子更大
largest = r # 更新最大位置
if largest == i: # 两个孩子都不比 i 大 → 堆序满足
break # 停止下沉
self.a[i], self.a[largest] = self.a[largest], self.a[i] # 与较大孩子交换
i = largest # 继续下沉
def push(self, x):
self.a.append(x) # 新元素放末尾
self._sift_up(len(self.a) - 1) # 从末尾上浮
def pop(self):
top = self.a[0] # 堆顶是最大值
last = self.a.pop() # 取出末尾元素
if self.a: # 堆非空
self.a[0] = last # 末尾元素搬到堆顶
self._sift_down(0) # 从堆顶下沉
return top # 返回最大值
def peek(self):
return self.a[0] # O(1) 查看堆顶(不删除)
# 测试:全部弹出应为从大到小的顺序
h = MaxHeap()
nums = [3, 1, 4, 1, 5, 9, 2]
for x in nums:
h.push(x) # 逐个入堆
out = []
while h.a: # 堆非空就弹出
out.append(h.pop()) # 每次弹最大值
print('手写大顶堆弹出顺序:', out) # 期望 [9, 5, 4, 3, 2, 1, 1](从大到小)
assert out == sorted(nums, reverse=True), 'MaxHeap 弹出顺序错误'
print('断言通过:大顶堆从大到小弹出 ✔')
h2 = MaxHeap()
h2.push(7); h2.push(10); h2.push(3)
print('peek(堆顶最大):', h2.peek()) # 10
assert h2.peek() == 10, 'peek 错误'
print('断言通过:peek 返回堆顶最大 ✔')
手写大顶堆弹出顺序: [9, 5, 4, 3, 2, 1, 1] 断言通过:大顶堆从大到小弹出 ✔ peek(堆顶最大): 10 断言通过:peek 返回堆顶最大 ✔
# ============== 小顶堆 + 懒删除(LazyHeap) ==============
# 【题目目标】实现带「懒删除」的小顶堆:堆删除任意元素的代价是 O(n)(要查找+
# 下沉),改为记账式删除——remove(x) 只计数不真删,pop 时统一把堆顶
# 中已被标记删除的元素清理掉
# 【算法思路】deleted 用 Counter 记录「每个值被标记删除的次数」;_clean() 在 pop
# 之前循环:只要堆顶是被删元素就弹出并销掉一条删除记录;size 维护逻辑
# 大小(含仍残留在堆中但已标记删除的元素),使 len(h) 语义正确
# 【变量含义】hp:真正存储元素的小顶堆;deleted:值 → 被标记删除次数的计数器;
# size:逻辑大小(含待清理元素);x:元素;_clean:清理方法
# 【循环不变量】pop 返回的永远是「未被标记删除」的最小值;deleted 计数与堆中
# 残留的待删元素一一对应
# 【递归终止】_clean 循环到堆空或堆顶不再是已删除元素为止
# 【关键边界】remove 只记账不真删(真删是 O(n) 就失去意义);remove 时 size 也要
# -1,否则 len(h) 与实际逻辑大小不符;同一值多次删除累计计数;pop 前
# 必须 _clean,否则可能返回已被删除的元素
# 【复杂度】push/remove 均摊 O(log n);被删元素实际出堆延迟到它浮到堆顶时
# 小顶堆 + 懒删除技巧:堆删除任意元素代价高,改成 Counter 记账、pop 时再统一清理堆顶
from collections import Counter
import heapq
# 小顶堆 + 懒删除:堆删除任意元素代价高,改成先记账、pop 时再统一清理
class LazyHeap:
"""小顶堆 + 懒删除:remove(x) 只记账不真删,pop() 前先清掉堆顶已删除元素。"""
def __init__(self):
self.hp = [] # 真正存储的堆(小顶堆)
self.deleted = Counter() # 每个值被标记删除的次数
self.size = 0 # 逻辑大小(含已标记删除的)
def push(self, x):
heapq.heappush(self.hp, x) # 正常入堆
self.size += 1 # 逻辑大小加 1
def remove(self, x):
self.deleted[x] += 1 # 不真正删除,先记账
self.size -= 1 # 逻辑大小减 1
def _clean(self):
while self.hp and self.deleted[self.hp[0]] > 0: # 堆顶是被删除的元素就弹出
self.deleted[heapq.heappop(self.hp)] -= 1 # 弹出并销掉一条删除记录
def pop(self):
self._clean() # 堆顶若已被删除,先清理掉
x = heapq.heappop(self.hp) # 弹出真正的最小值
self.size -= 1 # 逻辑大小减 1
return x # 返回弹出的元素
def __len__(self):
return self.size # 支持 len(h),返回逻辑大小
# 测试:删除 3 后弹出顺序应跳过 3
h = LazyHeap()
for x in [5, 3, 8, 1]:
h.push(x) # 依次入堆
print('push [5,3,8,1] 后 remove(3)(打标记,不真删)')
h.remove(3) # 懒删除 3
print('deleted 计数:', dict(h.deleted))
out = []
while h: # 依次弹出
out.append(h.pop())
print('pop 依次:', out) # 期望 [1, 5, 8],3 已被过滤
assert out == [1, 5, 8] and 3 not in out, '懒删除语义错误'
print('断言通过:remove 后 pop 不会返回被删元素 ✔')
push [5,3,8,1] 后 remove(3)(打标记,不真删)
deleted 计数: {3: 1}
pop 依次: [1, 5, 8]
断言通过:remove 后 pop 不会返回被删元素 ✔
§3 Top-K 模板:第 K 大 / 前 K 高频¶
215 数组中的第 K 个最大元素¶
思路:维护大小为 K 的小顶堆——堆里始终是「当前已见的前 K 大」,堆顶就是第 K 大:
hp = nums[:k]; heapq.heapify(hp)
for x in nums[k:]:
if x > hp[0]:
heapq.heapreplace(hp, x) # 弹出最小,压入更大
return hp[0]
复杂度(背):时间 $O(n \log k)$(每个元素至多一次替换 $O(\log k)$),空间 $O(k)$。
为什么比全排序好:$k \ll n$ 时省内存省时间;且支持流式(还可动态增删)。
347 前 K 个高频元素¶
两步:Counter 统计频次 → 大小为 K 的小顶堆按频次过滤:
$$\text{堆元素} = (\text{freq}, \text{num}), \quad \text{堆顶即当前第 K 高频的频次}$$
703 数据流中的第 K 大元素¶
思路:维护一个大小为 k 的小顶堆,堆里始终是已见数据中最大的 k 个,堆顶就是第 K 大。
新数到达时:堆未满直接 heappush;否则若 x > 堆顶 就 heapq.heappushpop(hp, x)(先压入 x 再弹走当前最小,等价于替换),堆顶保持第 K 大。
单次 add 为 $O(\log k)$,空间 $O(k)$,天然支持流式数据。
# ============== Top-K 两大模板:215 第 K 大 / 347 前 K 高频 ==============
# 【题目目标】① 215:求数组中第 K 大的元素;② 347:求出现频率前 K 高的元素
# 【算法思路】守门员模板:维护「大小为 k 的小顶堆」,堆里始终是当前已见的前 K 大,
# 堆顶就是第 K 大(门槛)——新元素比堆顶大就用 heapreplace 替换,否则
# 直接被淘汰;347 先 Counter 统计频次,再把 (freq, num) 放进小顶堆
# (按频次排序),堆超过 k 个就弹掉最小频次,剩下的就是前 K 高频
# 【变量含义】nums:数组;k:第 K / 前 K;hp:大小为 k 的小顶堆;x:当前元素;
# cnt:频次计数器;num/freq:元素与其频次
# 【循环不变量】堆大小恒 ≤ k;215 中 hp[0] 恒为当前第 K 大,347 中堆顶恒为
# 当前第 K 高频的频次
# 【递归终止】无递归;扫描完剩余元素 / Counter 全部项即结束
# 【关键边界】215 初始取前 k 个直接 heapify(比逐个 push 快);347 堆元素必须是
# (freq, num) 元组(比较时先比频次);heapreplace 要求堆非空;215 的
# k 是 1-based(第 K 大),堆大小必须恰为 k
# 【复杂度】时间 O(n log k),空间 O(k)
# Top-K 两大模板:215 第 K 大用「大小为 k 的小顶堆」当守门员;347 前 K 高频先 Counter 再按频次过滤
import heapq
from collections import Counter
# 215. 数组中的第 K 个最大元素:维护大小为 k 的小顶堆,堆顶就是第 K 大
# 思路:堆里只留当前已见的前 K 大;新元素比堆顶(门槛)大就替换,比门槛小直接淘汰
def find_kth_largest(nums, k):
hp = nums[:k] # 先取前 k 个建堆
heapq.heapify(hp) # 小顶堆,大小为 k
for x in nums[k:]: # 扫描剩余元素
if x > hp[0]: # 新元素比堆顶(当前第 K 大)大才可能进前 K
heapq.heapreplace(hp, x) # 弹出堆顶并压入 x(保持大小为 k)
return hp[0] # 堆顶就是第 K 大的元素
# 347. 前 K 个高频元素:先用 Counter 统计频次,再用大小为 k 的小顶堆按频次过滤
def top_k_frequent(nums, k):
cnt = Counter(nums) # 统计每个数出现的频率
hp = [] # (频率, 数),小顶堆
for num, freq in cnt.items(): # 遍历每个数及其频率
heapq.heappush(hp, (freq, num)) # 按频率入堆(频率小的排前面)
if len(hp) > k: # 堆超过 k 个就挤掉最小的
heapq.heappop(hp) # 弹掉当前最小频率
return [num for _, num in hp] # 堆里剩下的就是频率前 K 高的数
print('第3大:', find_kth_largest([3, 2, 1, 5, 6, 4], 3)) # 期望 4
print('第1大:', find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 1)) # 期望 6
print('前2高频:', sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2))) # 期望 [1, 2]
print('前1高频:', top_k_frequent([1], 1)) # 期望 [1]
print('复杂度: O(n log k) 时间, O(k) 空间')
第3大: 4 第1大: 6 前2高频: [1, 2] 前1高频: [1] 复杂度: O(n log k) 时间, O(k) 空间
§4 数据流中的中位数(LeetCode 295):双堆¶
题目:动态插入整数,随时查中位数。
思路:两个堆把数据对半分:
- 小顶堆
lo存较小的一半(用大顶堆实现,即存负数)——堆顶是较小半的最大值 - 大顶堆
hi存较大的一半(小顶堆)——堆顶是较大半的最小值
平衡不变量:$|len(lo) - len(hi)| \le 1$。
$$\text{median} = \begin{cases} lo[0] \ (\text{取负还原}) & \text{总数为奇数} \\ \dfrac{lo[0] + hi[0]}{2} \ (\text{注意 lo 存了负号}) & \text{总数为偶数} \end{cases}$$
复杂度:插入 $O(\log n)$,查中位数 $O(1)$。
# ============== 295 数据流中的中位数(双堆对半分) ==============
# 【题目目标】设计数据结构支持动态插入整数(add_num)并随时查询中位数
# (find_median,O(1))
# 【算法思路】两个堆把数据对半分:lo 存「较小的一半」(用大顶堆实现,即存负值,
# 这样堆顶是较小半的最大值)、hi 存「较大的一半」(小顶堆,堆顶是较大半
# 的最小值);每次 add:先进 lo → 把 lo 中最大(堆顶)挪到 hi → 若
# len(lo)<len(hi) 再挪回一个,保持平衡不变量 |len(lo)-len(hi)| ≤ 1;
# 总数为奇数时中位数 = -lo[0],偶数时 = 两堆顶的平均值
# 【变量含义】lo:较小一半(存负值的大顶堆);hi:较大一半(小顶堆);num:
# 新增的数;add_num 方法;find_median 方法
# 【循环不变量】|len(lo)-len(hi)| ≤ 1 且 lo 中所有元素 ≤ hi 中所有元素 → 中位数
# 必在两堆堆顶之间
# 【递归终止】无递归;add 的三步操作完成后状态即恢复平衡
# 【关键边界】lo 存的是负值,取回时必须取负还原(-lo[0]);奇偶判断看 len(lo)
# 是否 > len(hi);heappush + heappop 的组合写法保证先把新数放进正确半区
# 【复杂度】add O(log n),查询中位数 O(1),空间 O(n)
# 295. 数据流中的中位数:用两个堆把数据对半分,随时 O(1) 查中位数
# lo 存较小一半(用大顶堆实现,即存负数),hi 存较大一半(小顶堆);两堆大小差不超过 1
class MedianFinder:
def __init__(self):
self.lo = [] # 大顶堆(存负值):较小一半
self.hi = [] # 小顶堆:较大一半
def add_num(self, num):
heapq.heappush(self.lo, -num) # 先进较小半
heapq.heappush(self.hi, -heapq.heappop(self.lo)) # 把较小半最大挪到较大半
if len(self.lo) < len(self.hi): # 保持 lo >= hi
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def find_median(self):
if len(self.lo) > len(self.hi):
return float(-self.lo[0]) # 奇数:较小半堆顶
return (-self.lo[0] + self.hi[0]) / 2.0 # 偶数:两堆顶均值
mf = MedianFinder()
for x in [1, 2, 3]:
mf.add_num(x)
print('流 [1,2,3] 中位数 =', mf.find_median()) # 期望 2.0
mf.add_num(4)
print('流 [1,2,3,4] 中位数 =', mf.find_median()) # 期望 2.5
print('复杂度:add O(log n),查询 O(1)')
流 [1,2,3] 中位数 = 2.0 流 [1,2,3,4] 中位数 = 2.5 复杂度:add O(log n),查询 O(1)
§5 合并 K 个有序链表(LeetCode 23)¶
题目:合并 k 个有序链表为一个有序链表。
堆解法:把每个链表的当前头放进小顶堆,每次弹出最小并接上,再推进该链表:
复杂度:$O(N \log k)$(N 为总节点数),空间 $O(k)$。
对比:直接两两合并 $O(Nk)$;分治归并 $O(N \log k)$ 同堆。
💡 堆里不能直接存
ListNode(不可比较),要存(val, i, node)三元组加序号防比较冲突。
# ============== 23 合并 K 个有序链表(多路归并 + 小顶堆) ==============
# 【题目目标】把 k 个升序链表合并为一个升序链表
# 【算法思路】多路归并:把所有链表的「当前头节点」放进小顶堆,每次弹出值最小的
# 节点接到结果链表尾部,再把它在原链表中的下一个节点推入堆——堆中始终
# 保持每条链表尚未合并的最小候选
# 【变量含义】lists:k 个链表头组成的列表;hp:小顶堆;i:链表序号(防比较冲突);
# dummy/tail:虚拟头节点与结果尾指针;node:当前最小节点;nxt:它在原
# 链表中的下一个节点;ListNode:链表节点类;to_list:测试用工具函数,
# 把二维列表转成链表数组
# 【循环不变量】堆中恒为各链表尚未合并的最小节点 → 每次弹出的都是全局剩余最小
# (多路归并正确性的基础)
# 【递归终止】无递归;堆空即所有节点合并完毕
# 【关键边界】堆中不能存 ListNode 本身(对象不可比较会 TypeError),必须存
# (val, i, node) 三元组,i 保证两个相同 val 的节点也能比较;空链表头
# 不参与入堆;虚拟头节点简化空结果的处理
# 【复杂度】O(N log k) 时间(N 为总节点数)、O(k) 空间
# 23. 合并 K 个有序链表:把所有链表的当前头放入小顶堆,每次弹出最小并接上,再推进该链表
# 注意:堆里存 (val, i, node) 三元组,i 是链表序号,防止两个相同 val 的节点比较时报错
def merge_k_lists(lists):
hp = [] # 小顶堆
for i, head in enumerate(lists): # 遍历所有链表的头节点
if head is not None: # 非空链表才能入堆
heapq.heappush(hp, (head.val, i, head)) # 存入(值, 链表序号, 节点)
dummy = tail = ListNode(0) # 虚拟头节点,方便拼接结果
while hp: # 堆非空就继续
val, i, node = heapq.heappop(hp) # 弹出当前最小的节点
tail.next = node # 接到结果链表尾部
tail = tail.next # 尾指针后移
nxt = node.next # 该链表中它的下一个节点
if nxt is not None: # 该链表还没走完
heapq.heappush(hp, (nxt.val, i, nxt)) # 下一个节点入堆
return dummy.next # 返回合并后的链表头
# 链表节点定义(用于本地测试)
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val # 节点值
self.next = nxt # 指向下一个节点
# 工具函数:把形如 [[1,4,5],[1,3,4],[2,6]] 的二维列表转换成链表数组
def to_list(lists):
# 便利:[[1,4,5],[1,3,4],[2,6]] -> 链表数组
res = []
for a in lists: # 处理每个子列表
dummy = cur = ListNode(0) # 虚拟头,cur 指向当前链尾
for x in a: # 依次创建节点
cur.next = ListNode(x) # 接上新节点
cur = cur.next # 链尾后移
res.append(dummy.next) # 收集建好的链表
return res # 返回链表数组
# 测试:合并三个链表并遍历输出所有节点值
merged = merge_k_lists(to_list([[1, 4, 5], [1, 3, 4], [2, 6]]))
vals = []
while merged: # 遍历合并后的链表
vals.append(merged.val) # 收集节点值
merged = merged.next # 指针后移
print('合并后:', vals) # 期望 [1,1,2,3,4,4,5,6]
print('复杂度:O(N log k)')
合并后: [1, 1, 2, 3, 4, 4, 5, 6] 复杂度:O(N log k)
§6 堆排序(了解 + 手撕备选)¶
过程:建堆 → 反复把堆顶(最大/最小)交换到末尾并缩小堆:
$$\(1) \ \text{heapify}(O(n)) \quad (2) \ n-1 \ \text{次 pop}(O(n \log n)) \Rightarrow O(n \log n)$$
- 不稳定排序(相等元素相对顺序可能变)
- 原地排序空间 $O(1)$;Python 工程上用
sorted()(Timsort,稳定)
面试点:堆排序 vs 快排——堆排最坏 $O(n \log n)$ 但实际常数大且不稳定;快排平均更快,最坏 $O(n^2)$。
§7 常见 bug 与边界(面试踩坑区)¶
- 大顶堆用负数:
heapq只支持小顶堆,存-x取回时别忘了取负还原 - K 与下标混淆:第 K 大(1-based)≠ 第 len-k 小;
find_kth_largest堆大小要正好 k - heapreplace vs push+pop:
heapreplace(hp, x)= 弹顶 + 压入,比两次操作快;但要求 hp 非空 - 中位数堆失衡:插入后没保持
|len(lo)-len(hi)|<=1,奇偶判错 - ListNode 不可比较:直接
heappush(hp, node)会 TypeError(因为__lt__缺失)——存(val, i, node) - heapify 复杂度误判:面试答「建堆 O(n log n)」会扣分——是 $O(n)$
- 原地修改输入:
heappop改变列表;要保留原数据就 copy
§8 面试追问与扩展(加分项)¶
8.1 为什么 Top-K 用「大小为 k 的小顶堆」而不是「大顶堆」¶
要找前 K 大,堆里留最小元素当「门槛」:新元素比门槛大才替换;用大顶堆则需要把整个堆当「候选」,无法淘汰。
8.2 建堆为什么 O(n)¶
自底向上下沉:大多数节点在底层,下沉次数 = 高度,半层以上节点基本只下沉 1 次——总和收敛到 $O(n)$。
8.3 流式 Top-K / 中位数的工程意义¶
实时排行榜(直播热度)、监控指标、推荐漏斗——堆是应对「数据持续到来」的标准结构。
8.4 相关题¶
378 有序矩阵中第 K 小的元素、373 查找和最小的 K 对数字、264 丑数 II(堆/DP)
§9 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 数组中的第 K 个最大元素(LeetCode 215)
- 2. 前 K 个高频元素(347)
- 3. 数据流中的第 K 大元素(703)
- 4. 最后一块石头的重量(1046)
- 5. 最小栈(155,堆对比)
- 6. 数组中的第 K 小的元素(快速选择/堆,面试手撕)
- 7. 查找和最小的 K 对数字(373)
- 8. 根据字符出现频率排序(451)
- 9. 前 K 个最小数(排序/堆双向题)
- 10. 有序矩阵中第 K 小的元素(378)
L2 进阶(10 题)¶
- 11. 合并 K 个升序链表(23)
- 12. 数据流的中位数(295)
- 13. 滑动窗口最大值(239,堆/单调队列双解)
- 14. 出现次数最多的 K 个单词(692,堆 + 排序规则)
- 15. 丑数 II(264)
- 16. 会议室 II(253,堆解)
- 17. 任务调度器(621,贪心+堆)
- 18. 雇佣 K 名工人的最低成本(857,堆+贪心)
- 19. 最接近原点的 K 个点(973)
- 20. 最大堆手写(面试手撕)
L3 挑战(5 题)¶
- 21. 堆排序手写(稳定版/不稳定版说明)
- 22. K 个一组翻转链表 + 堆混合(困难题)
- 23. IPO(502,双堆贪心)
- 24. 课程表 III(630)
- 25. 天际线问题(218,扫描线+堆)
自测要点¶
- 5 分钟内盲写:215 的堆解法 + 347
- 讲清 heapify 为什么 O(n)、Top-K 为什么用<小顶堆>
- 能手写 295 双堆的平衡逻辑