优先队列

定义

优先队列是计算机科学中的一类抽象数据类型，它维护一个元素集合，其中每个元素都关联一个优先级或键值，取出元素时依据优先级而非到达次序来决定先后^[1]。这种数据结构属于抽象数据类型，只规定接口层面的操作与行为约定，不规定元素在内存中的具体组织方式，因此同一套接口可以由多种具体数据结构承担^[4]。

最核心的操作有两类：一是把带优先级的元素插入集合，二是取出并删除当前优先级最高的元素；此外通常还提供只读取最高优先级元素而不改动集合的查看操作，以及判空操作^[5]。按照优先级高低的解释方向，可分为最小优先队列与最大优先队列：前者把较小的键视为更高优先级，后者把较大的键视为更高优先级^[2]。当多个元素优先级相同时，它们的先后次序通常不作保证，可由实现任意决定^[6]。

原理

优先队列本身只是接口约定，其行为由底层实现决定。最简单的方式是用无序数组：插入时把元素放在末尾，代价为 $O(1)$，但查找最高优先级元素需要扫描整个数组，代价为 $O(n)$^[2]。另一种方式是维护有序数组，插入时用二分查找定位后仍需移动元素，代价为 $O(n)$，而取最值和查看均为 $O(1)$^[2]。这两种极端做法在插入与删除次数大致相当时都退化为 $O(n^2)$ 的总代价，因此常用结构介于两者之间^[2]。

最通行的实现是二叉堆（binary heap）：它是一棵近似完全的二叉树，并满足堆序性质，即每个节点的键都不小于（最小堆中为不大于）其子节点的键，故最值必然位于根^[3]。由于树形近似完全，节点可以直接存放在数组中，下标为 $i$ 的节点其子节点位于 $2i+1$ 与 $2i+2$，无需显式指针^[7]。插入时先把新元素放到保持形状不变的位置，再反复与父节点交换上浮；删除最值时把末尾元素移到根，再与优先级更高的子节点交换下沉，两者代价均为 $O(\log n)$^[8]。

各类实现的复杂度对照如下^[9]。

graph LR

A[插入元素] --> B[放入数组末尾]

B --> C{是否小于父节点}

C -->|是| D[与父节点交换]

D --> C

C -->|否| E[堆序恢复]

除二叉堆外，二项堆与斐波那契堆等结构提供了额外的能力：前者可在 $O(\log n)$ 时间内合并两个优先队列，后者使插入、取最值与修改优先级取得分摊常数时间^[1]。平衡二叉搜索树也能承担同一接口，插入与删除均为 $O(\log n)$，但常数因子与空间开销通常大于堆^[2]。

发展历程

堆作为优先队列的实现方式与堆排序相伴发展，堆排序被列为仅靠比较进行排序时渐进最优的算法之一，其建立在优先队列上的排序过程由 $n$ 次插入与 $n$ 次删除组成，总代价为 $O(n\log n)$^[7]。此后为改进合并操作等薄弱环节，出现了多种可合并堆结构^[3]。

二项队列由让·维耶曼（Jean Vuillemin）于 1978 年提出，它使插入、删除最值与合并都能在 $O(\log n)$ 时间内完成，弥补了普通二叉堆在合并上需 $O(n)$ 的不足^[3]。斐波那契堆进一步把插入、取最值和修改优先级降为分摊常数时间，删除仍为 $O(\log n)$，在图算法中用于改善理论复杂度^[1]。

应用

操作系统中的任务调度是典型场景，就绪任务按优先级组织成优先队列，调度器每次选取优先级最高的任务运行^[1]。事件驱动模拟同样依赖它：模拟器不必逐个时间片推进，而是用优先队列存放待处理事件，每次取出时间最早的事件并把时钟直接推进到该时刻^[10]。

在图搜索领域，迪杰斯特拉算法与普里姆算法都靠优先队列反复取出当前距离或代价最小的顶点，从而构成最小生成树与最短路径的计算框架^[6]。哈夫曼编码的构造过程每一次都要取出频率最小的两棵子树进行合并，用优先队列实现时整体时间为 $O(n\log n)$，其中 $n$ 为字符集大小^[7]。此外，在碰撞检测中维护物体下一次接触时刻、在数据流中保留最大的 $M$ 个数值等任务，也都可以借助优先队列完成^[4]。

局限

二叉堆只在插入、删除最值和查看最值上高效，合并两个优先队列却需要 $O(n)$ 时间，因为必须把规模较小的堆逐元素插入另一堆；若要求对数级的合并，必须改用二项堆、斜堆或配对堆等结构^[3]。同理，删除或修改任意指定元素的优先级也不在标准操作之内，堆中查找某个元素需按规模线性扫描，通常要另设字典记录元素位置才能做到对数时间^[10]。

优先队列只能给出当前的极值，无法回答“前 $k$ 个最大元素”“某个元素排第几”这类查询，这类需求需换用其他结构或额外统计信息，故其能力边界由接口本身限定^[5]。此外，同一优先级元素的相对次序不被保证，涉及严格先来先服务的场景需要把到达时间纳入优先级设计^[6]。堆排序虽最坏情况为 $O(n\log n)$ 且就地完成，但对元素的访问跨度较大，缓存局部性不及快速排序^[11]。

参见

• 堆 —— 优先队列最常用的底层实现结构，分为最大堆与最小堆。

• 队列 —— 遵循先进先出规则的线性结构，优先队列与之相对照。

• 迪杰斯特拉算法 —— 借助优先队列取出当前最短距离顶点的图搜索算法。

• 哈夫曼编码 —— 用优先队列反复合并最小频率子树的数据压缩方法。

• 堆排序 —— 以优先队列的插入与取最值操作为基础的就地排序算法。