堆、选择与流 · HTML
数学 / 逻辑形态
有 m 个非降序序列 S_j。堆保存每个非空来源的最前未消费项 (value,j,pos)。每次弹出全局最小项，仅把同一来源的下一项加入。
识别信号
- 输入由多个内部已有序的列表、链表、迭代器或文件组成。
- 全局下一小值一定在某个来源的当前头部。
- 只生成全局前 t 项，不值得摊平后全排序。
- 来源可惰性读取，无法同时装入内存。
- 候选结构是多条独立的递增链。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 来源内部无序 | 仅看头部无法保证全局最小；先排序各来源或改用普通选择结构。 |
| 一般图最短路 | Dijkstra 会松弛共享状态并处理多条到达路径；K 路归并的来源是固定、互不汇合的有序链。 |
| 只有两个内存数组 | 双指针归并 O(N) 且常数更小，无需堆。 |
核心不变量
对每个仍有剩余元素的来源，堆中恰有其最前未消费项；所有未输出元素的全局最小值必在堆中。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 大小至多 m 的小根堆，entry 为 (值/键, 来源编号, 来源内位置)。 |
| Transition | 弹出一个头部作为下一输出，推进它所属来源一格；未耗尽则加入新头部。 |
| Frontier / order | m 条有序链的头部集合；每次只扩展刚胜出的来源。 |
Python 骨架
from heapq import heappop, heappush
def merge_sorted(sources):
heap = []
for sid, seq in enumerate(sources):
if seq:
heappush(heap, (seq[0], sid, 0))
out = []
while heap:
value, sid, pos = heappop(heap)
out.append(value)
pos += 1
if pos < len(sources[sid]):
heappush(heap, (sources[sid][pos], sid, pos))
return out
正确性思路
- 每个来源未消费部分的最小值就是其头部。
- 全体未消费元素的最小值因此等于所有来源头部的最小值，heap pop 的下一输出正确。
- 弹出后只有胜出来源失去头部；推进它就恢复不变量。
复杂度
| Time | Space | Parameters |
|---|
| 输出 N 项 O(N log m)；只取 t 项为 O(m+t log m) | O(m)，不计输出 | m 为来源数，N 为总项数，t 为实际消费数。 |
边界条件
- sources 为空
- 部分来源为空
- 重复值
- 对象需要 tie-breaker
- 惰性迭代器不能按下标访问
错误模式
| Pattern | Why it fails / fix |
|---|
| 把整个来源压入堆 | 空间膨胀到 O(N)，失去只保留 m 个前沿的价值。 |
| 推进所有来源 | 只有胜出来源失去头部；推进其他来源会跳过尚未输出项。 |
| entry 不含来源身份 | 弹出后不知道推进哪条链；必须携带来源和位置/迭代器。 |
选择与排除规则
- 两个来源优先双指针。
- m 个有序来源且取全量或前缀：K 路归并堆。
- 惰性来源用迭代器 entry，不复制全序列。
- 候选链会汇合到共享状态时检查 Dijkstra。
相关模板
| Relation | Template | Boundary |
|---|
| composition | 链表指针改线 | 归并链表时，堆选择、指针改线负责拼接。 |
| contrast | Top-K 有界堆 | Top-K 淘汰候选；K 路归并保留每个来源的下一项。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 得到 [1,2,3,5,7,8]，堆从未超过 3 项。 |
| Setup | 三条时间流为 [1,8]、[2,3]、[5,7]。 |
| Trace | 头部 1,2,5 入堆；弹 1 后只加 8，随后弹 2、3、5、7、8。 |
Recall prompts
我的补充