优先队列
Priority Queue
约 12 分钟 · v11
优先队列
cs-ds/priority-queue · COMP25211 先看：急诊室不是"先来先看"，而是"最急先看"
候诊区里每个病人有个紧急度（5 最危急、1 最轻）。点「来个病人」加人，点「叫号」喊下一个——注意：叫到的不是排最前面的，而是紧急度最高的（橙框那个）。这就是优先队列和普通排队的根本区别。
急诊分诊台
候诊区按到达顺序排，但叫号永远叫紧急度最高的——所以队首不一定先走。紧急度相同时，按先来先走。这就是优先队列：出队的是"优先级最高"的，不是"最先进的"。
优先队列（Priority Queue）是一个 ADT，提供两个核心操作：insert(x, 优先级) 放入一个带优先级的元素、extractMax() 取出并删除当前优先级最高的元素。
和普通队列对比：普通队列是 FIFO（先进先出，出队首）；优先队列出队的是优先级最高者，与进入顺序无关。
2 先把它当 ADT：只认操作，不管怎么存
和"栈""队列"一样，优先队列首先是一组操作的约定（见 抽象数据类型）。用它的人只需要：
| 操作 | 承诺（契约） |
|---|---|
| insert(pq, x, pri) | 把元素 x 以优先级 pri 放进去 |
| extractMax(pq) | 取出并删除优先级最高的元素（空则报错） |
| peekMax(pq) / isEmpty(pq) | 看一眼最高优先级元素（不删）/ 是否为空 |
注意：ADT 只规定"取最高优先级"这个行为，没说内部怎么存。可以用数组、链表、堆……行为一样，但快慢天差地别。下一节就看怎么实现得快。
"最小优先"也一样（min-PQ，extractMin）——Dijkstra 里每次取"距离最小"的点用的就是它。最大还是最小，只是比较方向不同。
3 怎么实现得快：用堆
同一个优先队列接口，三种实现的快慢差很多。关键看两个高频操作 insert 和 extractMax：
| 实现 | insert | extractMax | 问题 |
|---|---|---|---|
| 无序数组 / 链表 | O(1) | O(n) | 取最大要扫一遍全部 |
| 有序数组 | O(n) | O(1) | 插入要挪位置保持有序 |
| 堆（heap） | O(log n) | O(log n) | 两个都快，整体最优 |
所以记住分两层：优先队列是"要什么"（ADT），堆是"怎么做到"（高效实现）。课程和题目常把两者并提，但它们是接口与实现的关系。细节见 堆。
4 自测
三道题，点选项即时判对错。
一句话带走：
优先队列 = 出队的是"优先级最高"的，不是"最先进"的（普通队列那才是 FIFO）。它是个 ADT：insert + extractMax + peekMax，只规定行为、不规定存法。实现里堆最划算——insert/extractMax 都 O(log n)，最大值恒在根、可用数组存、O(n) 建堆。分清两层：优先队列是接口，堆是实现。它支撑了堆排序、Dijkstra、Prim、霍夫曼编码等一大票算法。