优先队列

优先队列接口只要求选出“现在最该处理谁”，并不要求暴露完整排序；具体实现仍可以使用有序数组或搜索树。普通队列理路队列Queue · FIFO queue在队尾加入、从队首取出，并保持尚未离队元素的到达次序的抽象数据类型；循环数组和链表给出不同表示。按到达时间服务，优先队列按键服务；两个元素键相同时，谁先出来通常没有默认保证，除非接口另外要求稳定性。它也不是二叉堆理路二叉堆Binary heap用完全二叉树形状与父子堆序维护极值、常以数组隐式表示的数据结构。的同义词：堆是一种实现，正如数组或平衡树也可实现同一组操作。把接口与表示分开，才能根据工作负载选择结构——插入极多而只在末尾取一次最小值时，无序数组可能比堆更合适。

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

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

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

例如顶点 $v$ 初次得到距离 $10$，队列存入 $(10,v)$；后来经另一条路径改进为 $4$，再插入 $(4,v)$。先取出 $(4,v)$ 时处理其出边，最终取出 $(10,v)$ 时发现 $10\ne d[v]$，直接跳过，不再扫描出边。有效性判断依赖外部的当前距离表，单凭堆内记录无法知道哪个版本过时。在一般含平行弧的图中队列规模可达 $O(m)$，用二叉堆的相应成本应按 $\log (m+1)$ 计，而非不加说明地替换为 $\log n$。

有句柄的版本则让每个活动元素对应唯一记录。堆上交换两个元素后必须同时更新“句柄到位置”的映射，否则下一次减键会修改别的元素。元素身份、优先级和当前存储位置是三个不同对象，接口把它们区分开，才能正确支持可变优先级。

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

实现选择取决于操作频率和存储层。Fibonacci 堆理路Fibonacci 堆Fibonacci heap以延迟合并和级联切断取得常数摊还插入、合并与减键的可并优先队列。把合并与插入延迟化，在摊还意义下提供常数 insert、meld 和 decrease-key；Pairing Heap理路Pairing HeapPairing heap · 配对堆以一次根连接和两遍兄弟配对实现的自调整多叉堆，代码简洁且工程表现良好，但 decrease-key 的经典理论界需谨慎区分。保留简单的配对合并，但理论界与 Fibonacci 堆不完全相同；外存优先队列理路外存优先队列external-memory priority queue · I/O-efficient priority queue通过批量缓冲、分层下推与最小项物化，以块传输而非逐键访问衡量优先队列操作。则以批量缓冲和块传输降低 I/O，而不追求每个操作的 RAM 指令数。把上层算法的操作次数与实现的单次成本结合，才能得到总复杂度。

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

若算法需要频繁合并队列，meld 的成本会成为选择二项堆理路二项堆Binomial heap · 二项式堆以每个度数至多一棵二项树表示键集合，并像二进制进位一样连接同阶树以支持最坏对数时间合并与删除最小值。等结构的理由；若只需小规模固定键域，桶或原生数组可能已经足够。

Radix heap理路单调整数键的 Radix HeapRadix heap · 基数堆 · Binary radix heap在新键不小于最后弹出键的承诺下，按与该键的最高二进制差异位分桶，通过严格降桶的重分配跳过大片空键域。专门接受不小于最后弹出值的非负整数键，允许插入顺序下降到该界而不要求全程插入非降。它借XOR最高差异位分桶；普通表示的push/pop不能未经补证就继承任意减键、合并或peek接口。Dial环形桶理路Dial 环形桶最短路算法Dial's algorithm · Dial bucket queue · Dial算法在零至C的整数边权图中，用C+1个循环复用的距离桶实现Dijkstra，明确绝对距离游标、旧记录与O(n+m+nC)总成本。还利用活动键窗口宽C，用C+1槽保留真实绝对距离。