堆、选择与流 · HTML
数学 / 逻辑形态
给候选流 x1..xn 与全序 key(x)，求最大的 k 个。维护容量不超过 k 的 min-heap H；处理完前 i 项后，H 恰含该前缀最大的 min(k,i) 项。求最小 k 个时对称使用 max-heap。
识别信号
- 只要第 k 大/小或前 k 名，不要求其余元素的全序。
- 候选逐个到达，需要在线更新。
- 新候选只需和当前 Top-K 中最弱边界比较。
- k 明显小于 n，希望避免 O(n log n) 完整排序。
- 候选带复合键且最终只保留固定数量。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 静态数组只求一次第 k 项 | 允许改数组时 Quickselect 期望 O(n)，通常比 O(n log k) 更贴切；堆胜在在线、稳定和不改输入。 |
| 连续窗口的单个极值 | 固定窗口最大/最小值通常由 monotonic deque 线性解决，堆还需处理过期项。 |
| 需要全部有序输出 | 堆只保证偏序和边界；若最终仍要排所有项，直接排序更清楚。 |
核心不变量
处理完任意输入前缀后，堆内是该前缀最优的至多 k 个候选，堆顶是其中最容易被淘汰的边界。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 容量 k 的堆；entry 包含排序键、稳定 tie-breaker 与原对象。 |
| Transition | 堆未满则加入；已满且新项优于堆顶时用 heapreplace 淘汰并加入；否则丢弃。 |
| Frontier / order | 输入按任意顺序扫描；堆顶暴露当前选择边界，最终仅在需要有序展示时排序 k 项。 |
Python 骨架
from heapq import heappush, heapreplace
def top_k(items, k, key=lambda x: x):
if k <= 0:
return []
heap = []
for serial, item in enumerate(items):
entry = (key(item), serial, item)
if len(heap) < k:
heappush(heap, entry)
elif entry[:2] > heap[0][:2]:
heapreplace(heap, entry)
return [item for _, _, item in sorted(heap, reverse=True)]
正确性思路
- 空前缀时不变量成立。
- 堆未满时新项必属于当前前缀；堆已满时，不优于边界的新项不可能进入 Top-K，优于边界则只需替换最弱项。
- 归纳到完整输入，堆的成员恰为全局 Top-K；末尾排序只改变展示顺序。
复杂度
| Time | Space | Parameters |
|---|
| O(n log k)，若有序输出再加 O(k log k) | O(k) | n 为候选数，k 为保留数量。 |
边界条件
- k <= 0
- k >= n
- 键相同且对象不可比较
- 求最小 k 时堆方向相反
- 键含 NaN 或不能形成全序
错误模式
| Pattern | Why it fails / fix |
|---|
| 堆方向写反 | 求最大 k 个应维护小根堆，让最弱者在顶；求最小 k 才维护最大边界。 |
| 同键触发对象比较 | tuple 前缀相同后会比较 item；加入 serial 作为稳定且可比较的 tie-breaker。 |
| 把堆数组当排序结果 | 除堆顶外，数组下标不表示排名；需要顺序时单独排序堆中 k 项。 |
| 所有候选都 push-pop | 先和边界比较再 heapreplace，少做无意义堆操作并让意图更直接。 |
选择与排除规则
- 在线或 k << n：优先有界堆。
- 离线只求一个秩且允许改数组：比较 Quickselect。
- 仍需全部有序且 n 不大：直接排序。
- 滑动窗口 Top-1：先检查 monotonic deque。
相关模板
| Relation | Template | Boundary |
|---|
| frontier 排序 | 拓扑排序 / 入度消除 | 多个可执行任务还要按优先级选择。 |
| generalization | 双堆维护数据流中位数 | 持续维护中位边界而不是固定一侧的 k 项。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 保留 {6,7,9}，边界为 6。 |
| Setup | 评审分数依次为 6,2,9,7,5，只展示最高 3 个。 |
| Trace | 堆到 [2,6,9] 后，7 替换边界 2；5 不超过新边界 6，被丢弃。 |
Recall prompts
我的补充