优先队列

形式陈述 ​

最小优先队列是一种抽象数据类型公理库抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。：每个元素带有来自全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。键空间的优先级，核心操作为 insert(x,k)、find-min() 与 extract-min()，分别插入带键元素、读取最小键元素、读取并删除最小键元素。算法还可能要求 decrease-key(h,k')、delete(h) 或 meld(Q_1,Q_2)；这些操作需要什么句柄、是否允许重复键、空队列如何报告，都属于接口规格。最大优先队列只需反转键的次序。

同一接口可由不同表示实现，典型最坏时间如下；表中有序数组把最小元放在便于从末端删除的一侧，二叉堆的 decrease-key 已知目标位置。

实现	insert	find-min	extract-min	decrease-key
无序数组	$O(1)$	$O(n)$	$O(n)$	$O(1)$（有句柄）
有序数组	$O(n)$	$O(1)$	$O(1)$	$O(n)$
二叉最小堆	$O(\log n)$	$O(1)$	$O(\log n)$	$O(\log n)$

这些复杂度描述实现而非 ADT 本身；接口只规定可观察行为，除非成本界被明确写入规格。

直觉 ​

优先队列不维护完整排序，只维护“现在最该处理谁”这一条信息。普通队列按到达时间服务，优先队列按键服务；两个元素键相同时，谁先出来通常没有默认保证，除非接口另外要求稳定性。它也不是二叉堆公理库二叉堆Binary heap以近完全二叉树表示并满足父子堆序的优先队列结构。的同义词：堆是一种实现，正如数组或平衡树也可实现同一组操作。把接口与表示分开，才能根据工作负载选择结构——插入极多而只在末尾取一次最小值时，无序数组可能比堆更合适。

这一抽象尤其适合“候选会不断出现，但每一步只需要当前最好者”的算法。它避免提前为尚未需要的相对次序付费，又把取最优候选的规则集中在一个接口中。

例子与边界 ​

在非负权图的 Dijkstra 算法公理库Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。中，队列元素是尚未定型的顶点，键是当前暂定距离。每轮 extract-min 取出距离最小的顶点；松弛一条边若降低了邻点距离，具有句柄的实现可调用 decrease-key。此时键不是顶点固有属性，而是算法状态的一部分，随着松弛逐步减小。

若库的优先队列没有 decrease-key，可在距离降低时插入一条新记录，取出记录时再检查它是否等于当前距离；旧记录成为惰性丢弃项。这仍能得到正确的 Dijkstra 实现，但队列中会同时存在同一顶点的多个版本，操作次数与空间上界也随之改变，不能把它当作原接口的零成本替换。

优先级相同不意味着先进先出。若任务调度必须在同优先级内保持提交顺序，可把键扩展为 (priority, sequence_number)，或要求稳定优先队列。另一个边界是偏序键：若某些键不可比较，find-min 可能有多个互不支配的候选；本页的单一最小元接口依赖全序，偏序前沿需要另一个 ADT。

推论与应用 ​

二叉堆公理库二叉堆Binary heap以近完全二叉树表示并满足父子堆序的优先队列结构。以紧凑数组和堆序实现常用的对数时间版本。Dijkstra 与 Prim 算法公理库Prim 算法Prim's algorithm从一个顶点开始反复加入跨越当前割的最轻边的最小生成树算法。的复杂度会随优先队列实现改变；扫描线公理库扫描线范式Sweep-line paradigm · Plane sweep按事件推进一条虚拟直线，并用动态有序状态维护当前横截面组合关系的计算几何范式。则用它按坐标管理尚未发生的几何事件。只有把各算法的操作次数与所选实现成本相乘，复杂度结论才完整。

若算法需要频繁合并队列，meld 的成本会成为选择二项堆等结构的理由；若只需小规模固定键域，桶或原生数组可能已经足够。数据结构应由实际使用的操作组合决定，而不是由“优先队列通常就是堆”的惯性决定。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 6, heaps and priority queues。
• Erik D. Demaine and Charles E. Leiserson, MIT 6.046J, Priority Queues, lecture notes，priority-queue operations and implementation trade-offs。