专题进阶 · 栈与队列进阶推荐总顺序 · 第 43 / 148 课

将抽象操作与堆实现分开,利用稳定的优先级键处理任务。

先学会这些,再进入本课 堆
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 栈与队列进阶

优先队列Priority Queue

每次弹出优先级最高的元素,常用二叉堆实现。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

将抽象操作与堆实现分开,利用稳定的优先级键处理任务。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 堆顶为最小键。
  2. 键以优先级和唯一序号构成全序,因此同级先到先出。
  3. 每次 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

同级任务为何需要序号?

需要一点提示

任务可能不是可比较类型。

查看解析与答案

序号既保证稳定性,也使元组比较不必触及任务对象。

练习 2 · 边界与辨析

最大优先级数值先出怎么实现?

需要一点提示

转化排序键。

查看解析与答案

数值优先级可存负值;必须明确数字越大还是越小表示更高优先级。

练习 3 · 变式与迁移

把队内任务的 priority 字段改掉会自动上浮吗?

需要一点提示

堆有没有收到操作?

查看解析与答案

不会,需要显式更新堆位置或加入新版本并过滤旧记录。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。