堆与稳定优先队列
本节目标
理解堆只维护局部顺序，能用 heapq 在当前已就绪任务中反复取得最高优先级项，并为同优先级、不可比较 payload、取消和饥饿写明策略。
堆不等于排序列表
Python heapq 默认实现最小堆：
heap[0]是最小元素；heappush、heappop为 ；- 查看最小项为 ；
heapify(items)原地建堆为 ；- 除顶部外，列表整体不保证排序。
import heapq
ready = [(3, "review"), (1, "validate"), (2, "extract")]
heapq.heapify(ready)
while ready:
print(heapq.heappop(ready))若只需把全部数据排序一次，用 sorted 更直接；若在持续加入任务的同时反复取最小/最大，堆才体现价值。
优先级方向必须写清
最小堆先弹出较小值。本库约定“数值越小越紧急”：
heapq.heappush(ready, (1, "urgent"))Python 3.14 新增 heapify_max、heappush_max、heappop_max 等最大堆 API。为了兼容 Python 3.11+ 且保持一套心智模型，本课程主线仍使用最小堆；真实项目应按支持版本选择，不要混用正负号和 max-heap 语义。
同优先级需要稳定平局规则
直接存 (priority, task) 时，优先级相同会继续比较 task；不可比较对象可能抛 TypeError。加入单调序号：
import heapq
from itertools import count
sequence = count()
ready: list[tuple[int, int, str]] = []
heapq.heappush(ready, (2, next(sequence), "task-b"))
heapq.heappush(ready, (2, next(sequence), "task-a"))
_, _, first = heapq.heappop(ready)
print(first) # task-b：同优先级按入堆顺序这是 FIFO 平局策略。也可以使用任务 ID 形成与输入顺序无关的确定性；两者语义不同，必须在接口和测试中固定。若把 payload 对象放在最后，前面的字段必须能唯一打破平局，才不会比较 payload。
更新与删除为什么麻烦
heapq 没有按 ID 的高效任意删除/降优先级接口。常见做法是：
- 用字典保存
task_id → 当前有效条目/版本； - 更新时压入新条目，把旧条目标记失效；
- 弹出时跳过失效条目；
- 必要时重建堆控制垃圾条目。
这叫惰性删除。它增加字典 + 堆的一致性不变量；小项目若更新很少，重新建堆可能更清楚。不要直接在堆列表中修改任意元素而不重新恢复堆不变量。
优先级只比较当前已就绪项
依赖任务调度中，高优先级任务若前置依赖未完成，不能越过依赖执行。图决定“谁已就绪”，堆只在 ready 集合中选下一项。数据结构组合后，每一层仍有独立职责。
饥饿、公平与生产边界
持续到来的高优先级任务可能让低优先级任务长期不执行。可选策略：
- 等待时间增加后提升有效优先级（aging）；
- 每个优先级独立配额/轮转；
- 设置最大等待时间；
- 将紧急通道与普通通道分开并监控。
内存堆不提供持久化、租约、确认、重试或多进程一致性。它只是优先选择结构，不是生产消息系统。
练习
- 实现
(priority, sequence, task_id)队列，证明同优先级按入队顺序。 - 改成
(priority, task_id)，说明输出确定性与 FIFO 的差别。 - 把两个不可比较的字典作为 payload，证明唯一序号避免比较 payload。
- 设计惰性删除条目的字段和三个不变量。
- 为连续高优先级到达设计一种防饥饿策略，并写出可能的副作用。
自测
- 堆是否保证整个内部列表已排序？
-
heapify与逐项heappush的建堆成本有何不同？ - 为什么同优先级任务需要第二排序键？
- 任意修改
heap[index]后为什么可能错误？ - 优先级能否让未满足依赖的任务提前执行？
下一步与相关概念
参考资料
获取日期：2026-07-14。