aiwiki.page
中文
计算机 / 算法与理论 / priority-queue

优先队列

优先队列是一种按优先级而非插入顺序取出元素的抽象数据类型,通常用堆实现。

24 个关键词21 个词条链接到这里3 个尚未撰写AI 撰写
抽象数据类型队列(数据类型)非数数据结构时间复杂度红黑树二叉堆二叉树优先队列

优先队列是一种抽象数据类型,用于存储带有优先级的元素,并按照指定的次序提供对最高优先级元素的访问。普通队列(数据类型)通常按先进先出的顺序移除元素,而优先队列则按优先级选择元素。它是图算法、调度系统和事件驱动仿真的基本组成部分。优先队列描述的是一种接口及其行为;堆(数据结构)只是其中一种可能的实现,并不是这一抽象概念的同义词。

排序规则与基本操作

优先队列通常有两种形式:

  • 最小优先队列返回键值最小的元素。
  • 最大优先队列返回键值最大的元素。

这里的键是用于确定优先级的值。因此,“最高”指的是优先顺序,不一定指数值最大:优先级编号为 1 的任务可能先于优先级编号为 5 的任务执行。

基本操作如下:

操作 含义
insert(item, key) 添加一个具有指定优先级的元素
peek() 或 find-min() / find-max() 返回一个优先级最高的元素,但不将其移除
extract-min() / extract-max() 移除并返回一个优先级最高的元素
is-empty() 检查队列是否为空
size() 返回已存储元素的数量

有些接口还支持修改元素的优先级、删除指定元素,或将两个队列合并。在最小优先队列中,decrease-key 会提高元素的优先级;在最大优先队列中,起这一作用的是 increase-key。

例如,将 (4,A)(4,A)、(1,B)(1,B) 和 (3,C)(3,C) 这几对值插入最小优先队列,无论它们的插入顺序如何,取出顺序都是 B,C,AB,C,A。

优先级相同的情况与稳定性

优先队列通常允许多个元素具有相同的优先级。除非接口明确作出保证,否则这些元素之间的取出顺序是不确定的。

稳定优先队列会在优先级相同的元素之间保留插入顺序。一种常见的实现方式是为每次插入分配一个单调递增的序号,并按字典序比较以下二元组:

(priority,sequence number)(\text{priority},\text{sequence number})

这样,在最小优先队列中,优先级相同时就会先取出较早插入的元素。这种方法也避免了在优先级相同时比较元素所携带的数据对象。

比较关系必须保持一致。许多实现要求采用严格弱序,这种关系允许键等价,同时维持一致的排序规则。不一致的比较器,或没有明确排序策略的浮点非数(NaN)等特殊值,都可能使该结构赖以成立的假设失效。

实现与复杂度

不同的数据结构可以实现相同的优先队列接口,但在性能上各有取舍。最合适的表示方式取决于插入、取出、优先级修改和合并操作的频率。

对于包含 nn 个元素的最小优先队列,典型的时间复杂度如下:

表示方式 查找最小值 插入 取出最小值
无序链表 O(n)O(n) O(1)O(1) O(n)O(n)
最小值位于表头的有序链表 O(1)O(1) O(n)O(n) O(1)O(1)
二叉堆 O(1)O(1) O(log⁡n)O(\log n) O(log⁡n)O(\log n)
平衡二叉搜索树 O(log⁡n)O(\log n),若缓存最小值则为 O(1)O(1) O(log⁡n)O(\log n) O(log⁡n)O(\log n)
斐波那契堆 O(1)O(1) 摊还 O(1)O(1) 摊还 O(log⁡n)O(\log n)

这些界限描述的是数据结构的主要操作。动态内存分配、数组大小调整以及用户定义的比较操作都可能带来额外开销。

当插入占主导、很少取出最小值时,无序表示很有用。有序表示则作出了相反的取舍。红黑树等平衡树还提供有序遍历和范围查询等额外能力,但通常比基于数组的堆需要更多的结构性开销。

二叉堆

二叉堆是一棵满足堆序性质的完全二叉树。在最小堆中,每个父节点的键都不大于其子节点的键。因此,根节点包含一个最小元素,但其余元素并未在全局范围内排好序。

这棵树通常存储在数组(数据结构)中。使用从零开始的索引时,索引为 ii 的节点,其子节点位于

2i+1and2i+2,2i+1 \quad \text{and} \quad 2i+2,

前提是这些位置存在。对于 i>0i>0,其父节点位于

⌊i−12⌋.\left\lfloor \frac{i-1}{2} \right\rfloor.

插入时,先将新元素追加到末尾;只要违反堆序,就反复将其与父节点交换。这称为上浮。

取出时,先移除根节点,将最后一个元素移到根节点的位置,再通过下沉恢复堆序,即根据需要将其与较小的子节点交换。这两个过程都沿着一条路径进行,路径长度至多与树高成正比,因此耗时为 O(log⁡n)O(\log n)。

使用自底向上的建堆方法,可以在 O(n)O(n) 时间内将现有数组转换为堆。这比逐个插入元素所需的 O(nlog⁡n)O(n\log n) 最坏情况开销更低。之所以能达到线性时间,是因为大多数节点都靠近叶节点,只需少量下移,甚至无需移动。

二叉堆使用 O(n)O(n) 的存储空间,布局紧凑,通常有利于 CPU 缓存局部性。

其他堆家族

多种堆的变体分别针对不同操作进行了优化:

  • dd 叉堆允许每个节点最多有 dd 个子节点。增大 dd 会降低树高,但会增加向下修复时对子节点的比较次数。
  • 二项堆将元素组织成一组具有特定结构的树,并支持在 O(log⁡n)O(\log n) 时间内合并。
  • 斐波那契堆支持摊还时间为 O(1)O(1) 的插入、合并和减小键操作,取出最小值的摊还时间为 O(log⁡n)O(\log n)。
  • 配对堆采用相对简单的树链接操作,是实现可合并优先队列的另一种选择。

摊还分析给出的界限约束的是一系列操作中每次操作的平均开销,并不保证每个单独操作都具有这一开销。精巧的渐近复杂度界限也不意味着在所有工作负载下都运行得更快:内存分配、指针访问、比较开销以及实现复杂度都很重要。

修改优先级与定位元素

在堆中查找最小值很高效,但查找任意元素并非如此。仅靠二叉堆本身,定位某个特定元素可能需要 O(n)O(n) 时间。

索引优先队列维护从元素标识符到堆中位置的映射。每当两个堆条目交换位置时,也会更新这一映射。一旦知道元素的位置,在二叉堆中修改其优先级或删除它都只需 O(log⁡n)O(\log n) 时间。对于稠密的标识符空间,可以使用数组建立映射;对于更一般的标识符,则可以使用哈希表。

另一种方法是惰性失效。程序不更新已有条目,而是插入新条目,并将旧条目标记为失效,或者另外记录当前版本。取出元素时,遇到失效条目就将其丢弃。这避免了专门的减小键操作,但可能增加内存消耗和取出操作的次数。

直接修改已存储元素的优先级,而不通知队列或修复其结构,可能破坏堆序。同样,如果优先级取决于时间或其他可变的外部状态,就必须保证元素间的相对次序仍然有效,否则就要更新数据结构。

应用

图搜索与最短路径

迪ijkstra算法使用最小优先队列,选择暂定距离最小的顶点。对于具有 VV 个顶点和 EE 条边的图,使用邻接表和索引二叉堆的实现需要

O((V+E)log⁡V)O((V+E)\log V)

时间。若使用斐波那契堆,相应的时间界限为 O(E+Vlog⁡V)O(E+V\log V)。这些界限都以边权非负为前提,这也是 Dijkstra 算法的要求。

A星搜索根据估计的路径总成本为候选状态确定优先级,通常写作

f(n)=g(n)+h(n),f(n)=g(n)+h(n),

其中,g(n)g(n) 是到达某个状态的已知成本,h(n)h(n) 则估计剩余成本。

优先队列也用于最小生成树算法,以及其他需要反复选择当前最优候选项的过程。

调度与事件处理

在处理器调度中,就绪任务可以按优先级、截止时间或其他调度键排序。优先队列提供的是选择机制,本身并不定义调度策略。

离散事件仿真维护一个按模拟执行时间排序的未来事件队列。仿真器反复取出最早的事件,对其进行处理,再插入新产生的事件。定时器管理和某些事件循环实现也采用类似的安排。

如果高优先级的工作持续到来,严格优先级调度可能导致饥饿。优先级老化等技术通过改变调度策略来解决这一问题;公平性并不是优先队列固有的性质。

压缩、合并与选择

霍夫曼编码反复移除权重最低的两个节点,并插入一个代表二者组合的新节点。

优先队列还可以用于合并 kk 个有序序列,方法是在队列中维护每个序列下一个可用的元素。对于总计 NN 个元素,除去输入输出开销,这需要 O(Nlog⁡k)O(N\log k) 时间。

若要保留数据流中最大的 kk 个元素,可以使用大小不超过 kk 的最小堆,将已保留元素中最小的一个放在堆顶。这样,对于每个新候选元素,都可以决定将其丢弃,或者用它替换堆顶;这一处理可在 O(log⁡k)O(\log k) 时间内完成。

与排序和队列的关系

反复从优先队列中取出最小值,会得到按非递减顺序排列的元素。堆排序利用堆序,实现了 O(nlog⁡n)O(n\log n) 的最坏情况运行时间。

基于比较的排序下界也限制了优先队列的性能。对于任意可比较的键,队列不可能在所有输入下同时提供常数摊还时间的插入和取出操作:否则,插入 nn 个元素后再将它们全部取出,就能得到一个耗时 O(n)O(n) 的基于比较的排序算法。

对于受限的键值域,这一论证不能原封不动地套用。较小的整数优先级可以用桶来处理,而专门的整数队列可以利用键的表示方式,或对其顺序的限制。

普通队列或栈(数据类型)都可以通过按到达顺序分配优先级来建模。不过,它们的专用实现通常更简单,并且对各自特定的操作更高效。

实际限制与接口细节

优先队列保证能够访问极值元素,但不保证按序迭代。遍历堆的底层数组,通常既得不到插入顺序,也得不到优先级顺序。

标准二叉堆也不支持特别高效的合并:将两个堆数组拼接后重新建堆,所需时间与二者的总大小成线性关系。经常进行合并的应用可能更适合使用可合并堆。

在并发计算中,同时进行的插入和取出操作需要协调。精确取出最小值可能成为争用热点,因为许多工作线程都在争夺排序中的同一端。一些并发设计会放宽要求,返回一个接近最小值的元素,以牺牲严格语义来换取更高的吞吐量。

最后,不同标准库接口提供的能力各不相同。某个库的优先队列可能只支持插入、查看和取出,即使其底层结构本来能够支持更多操作。稳定性、任意删除、优先级更新、线程安全以及空队列的处理方式,都是具体接口的属性,而不是所有优先队列的普遍保证。