Olverae Assets

1 先看：急诊室不是"先来先看"，而是"最急先看"

候诊区里每个病人有个紧急度（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)	两个都快，整体最优

为什么是堆

二叉堆是一棵"父节点总 ≥ 孩子"的完全二叉树（大根堆）。最大值永远在根，所以 peekMax 是 O(1)；insert 和 extractMax 靠"上浮 / 下沉"沿树高调整，只走 O(log n) 层。

还能塞进数组

完全二叉树可以用一个数组表示（下标 i 的孩子在 2i、2i+1），不需要真的指针节点——省内存又对缓存友好。

建堆很快

把 n 个元素一次性建成堆只要 O(n)（自底向上）。堆排序、Dijkstra、Prim、霍夫曼编码，背后都站着优先队列。

所以记住分两层：优先队列是"要什么"（ADT），堆是"怎么做到"（高效实现）。课程和题目常把两者并提，但它们是接口与实现的关系。细节见堆。

4 自测

三道题，点选项即时判对错。

去做例题：用堆实现一个优先队列（insert / extractMax）

去做例题

一句话带走：

优先队列 = 出队的是"优先级最高"的，不是"最先进"的（普通队列那才是 FIFO）。它是个 ADT：insert + extractMax + peekMax，只规定行为、不规定存法。实现里堆最划算——insert/extractMax 都 O(log n)，最大值恒在根、可用数组存、O(n) 建堆。分清两层：优先队列是接口，堆是实现。它支撑了堆排序、Dijkstra、Prim、霍夫曼编码等一大票算法。