01先把问题说具体
任务不断到来,每次应先处理优先级数值最小的任务;相同优先级按提交顺序处理。
02一步步得到方法
优先队列规定接口,不规定存储布局
普通队列按到达次序取出,优先队列按键值取出。二叉堆是常见实现,但有序数组、平衡树也可以实现相似接口,代价不同。知道堆的局部顺序后,就能解释为何不必始终完整排序。
Python heapq 默认小根堆。存 (priority,sequence,task),先比较优先级,再比较递增序号,从而稳定处理同优先级任务,并避免比较任务对象本身。
优先级改变需要维护结构
堆不会感知你在外部修改对象字段。常见办法是插入新的 (优先级,版本,任务) 记录,弹出时检查版本,过期记录丢弃;Dijkstra 的堆实现常使用类似的惰性删除。
这里先学习不修改已入队键的基本版本。若需要 decrease-key,可维护元素到堆下标的索引,并在键改变后上浮或下沉。
队列接口与具体实现分开
优先队列定义插入、查看最高优先项、取出最高优先项等行为;二叉堆只是常见实现。相同接口可以基于有序数组、树或其他堆,复杂度和支持操作不同。
优先级相同时若载荷不可比较,堆中的元组应加入递增序号作为平局键,避免继续比较载荷而报错。修改队内元素的优先级也不能只改字段,必须恢复结构或采用惰性失效记录。
03把一个小例子完全算清楚
依次提交 (2,A)、(1,B)、(1,C)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 入 A | (2,0,A) | 序号 0 |
| 入 B、C | 最小键 (1,1,B) | 同优先级 B 早于 C |
| 第一次弹出 | B | 优先级较高,即数值较小 |
| 继续弹出 | C、A | 同级按提交顺序 |
窄屏可左右滑动表格,阅读完整计算与理由。
排序规则必须成为可比较的键;任务负载本身不应意外参与比较。
04为什么这个方法成立
- 堆顶为最小键。
- 键以优先级和唯一序号构成全序,因此同级先到先出。
- 每次 pop 后堆恢复性质,下一次仍返回剩余任务中最优者。
05把推导翻译成代码
Python · 可独立运行的教学实现
import heapq
class TaskQueue:
def __init__(self):
self.heap = []
self.sequence = 0
def push(self, priority, task):
heapq.heappush(self.heap, (priority, self.sequence, task))
self.sequence += 1
def pop(self):
return heapq.heappop(self.heap)[2]逐个理解关键决定
self.sequence- 打破同优先级平局,避免字符串等任务负载被用作无意的第二排序键。
heapq.heappop- 移除最小键并修复堆,不是简单删掉数组第 0 个位置。
06时间、空间与实现范围
入队与出队 O(log n),查看堆顶 O(1),堆空间 O(n)。
批量 heapify 是 O(n),逐次 push 建队列通常 O(n log n)。本接口空队 pop 会抛 IndexError。
07改变条件,检查哪里会出错
遍历底层 heap 就得到全序
只能保证根最小,完整有序输出需要持续 pop。
把堆数组当作完整排序结果
堆只保证父子约束,遍历内部数组不等于按优先级输出,需反复取堆顶。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
同级任务为何需要序号?
需要一点提示
任务可能不是可比较类型。
查看解析与答案
序号既保证稳定性,也使元组比较不必触及任务对象。
最大优先级数值先出怎么实现?
需要一点提示
转化排序键。
查看解析与答案
数值优先级可存负值;必须明确数字越大还是越小表示更高优先级。
把队内任务的 priority 字段改掉会自动上浮吗?
需要一点提示
堆有没有收到操作?
查看解析与答案
不会,需要显式更新堆位置或加入新版本并过滤旧记录。