优先队列
复习
- 删除节点与树的退化：插入顺序不好会退化成链表
- 平衡树（进阶）：平衡树通过旋转，让树始终保持矮而匀称
- 堆：父不大于子，堆顶是最值
TL;DR
- 优先队列每次取出优先级最高的元素
- 它不按进入顺序，而按优先级
- 用堆实现时，取最值
O(1)，插入删除O(log n) - 调度、事件模拟、最短路都会用到它
正文
普通队列讲究“先来先服务”。可现实里，很多事情并不该按先来后到办，而是“谁更紧急，谁先来”。这种结构，就是优先队列（priority queue）。
按优先级，而不是按顺序
优先队列的规则很简单：每次取出优先级最高（或最低）的那个元素。
它和普通队列的差别一目了然：
- 普通队列：先进先出，看的是到达时间
- 优先队列：看的是优先级，后到的急事也可能先被处理
它通常支持两个核心操作：
- 插入一个带优先级的元素
- 取出当前优先级最高（最低）的元素
用堆来实现
优先队列只是一个抽象，规定了“能做什么”。而它最经典的实现，正是上一章的堆。
为什么堆特别合适？因为堆的堆顶，恰好就是最小（或最大）值：
- 取最值：直接看堆顶，
O(1) - 插入：上浮调整，
O(log n) - 取出最值：拿走堆顶再下沉调整，
O(log n)
“随时能拿到最值”这个能力，与优先队列的需求完美对应。用堆来实现它，既高效又简洁。
它出现在哪里
优先队列的用武之地很广，本质都是“按重要性排队”：
- 任务调度：优先级高的任务先执行
- 事件驱动模拟：按事件发生的时间顺序处理
- 最短路算法：每次都取出当前最近的节点（后面会讲到）
你会发现，这些场景的共同点是：需要反复地“取出当前最优/最急”。 一旦问题落到这个模式上，优先队列往往就是那把趁手的工具。
这一章之后，“树与优先级”这一组就告一段落。下一章，我们回到字符串，看看一种专为前缀而生的树。
思考题 1
优先队列和普通队列，在“谁先被取出”上有什么不同？
思考题 2
为什么用堆来实现优先队列很合适？
小结
知识点
- 优先队列按优先级而非到达顺序取出元素
- 核心操作是插入与取出最值
- 用堆实现：取最值
O(1)，插入删除O(log n) - 用于调度、事件模拟与最短路算法
参考资料
- Wikipedia(zh)：优先队列：按优先级取出元素的抽象数据类型
- Wikipedia(zh)：二叉堆：优先队列的经典实现
思考题答案（仅供参考）
思考题 1
普通队列按到达顺序取出，先进先出；优先队列按优先级取出，谁最重要谁先出，与进入顺序无关。后到的紧急任务也可能先被处理。
思考题 2
因为优先队列需要的正是“快速取出当前最值”，而堆的堆顶恰好是最值：取堆顶 O(1)，插入和删除后通过上浮、下沉调整维持堆序，代价 O(log n)。两者需求与能力高度吻合。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪