优先队列是一种抽象数据类型,用于存储带有优先级的元素,并按照指定的次序提供对最高优先级元素的访问。普通队列(数据类型)通常按先进先出的顺序移除元素,而优先队列则按优先级选择元素。它是图算法、调度系统和事件驱动仿真的基本组成部分。优先队列描述的是一种接口及其行为;堆(数据结构)只是其中一种可能的实现,并不是这一抽象概念的同义词。
排序规则与基本操作
优先队列通常有两种形式:
- 最小优先队列返回键值最小的元素。
- 最大优先队列返回键值最大的元素。
这里的键是用于确定优先级的值。因此,“最高”指的是优先顺序,不一定指数值最大:优先级编号为 1 的任务可能先于优先级编号为 5 的任务执行。
基本操作如下:
| 操作 | 含义 |
|---|---|
insert(item, key) |
添加一个具有指定优先级的元素 |
peek() 或 find-min() / find-max() |
返回一个优先级最高的元素,但不将其移除 |
extract-min() / extract-max() |
移除并返回一个优先级最高的元素 |
is-empty() |
检查队列是否为空 |
size() |
返回已存储元素的数量 |
有些接口还支持修改元素的优先级、删除指定元素,或将两个队列合并。在最小优先队列中,decrease-key 会提高元素的优先级;在最大优先队列中,起这一作用的是 increase-key。
例如,将 、 和 这几对值插入最小优先队列,无论它们的插入顺序如何,取出顺序都是 。
优先级相同的情况与稳定性
优先队列通常允许多个元素具有相同的优先级。除非接口明确作出保证,否则这些元素之间的取出顺序是不确定的。
稳定优先队列会在优先级相同的元素之间保留插入顺序。一种常见的实现方式是为每次插入分配一个单调递增的序号,并按字典序比较以下二元组:
这样,在最小优先队列中,优先级相同时就会先取出较早插入的元素。这种方法也避免了在优先级相同时比较元素所携带的数据对象。
比较关系必须保持一致。许多实现要求采用严格弱序,这种关系允许键等价,同时维持一致的排序规则。不一致的比较器,或没有明确排序策略的浮点非数(NaN)等特殊值,都可能使该结构赖以成立的假设失效。
实现与复杂度
不同的数据结构可以实现相同的优先队列接口,但在性能上各有取舍。最合适的表示方式取决于插入、取出、优先级修改和合并操作的频率。
对于包含 个元素的最小优先队列,典型的时间复杂度如下:
| 表示方式 | 查找最小值 | 插入 | 取出最小值 |
|---|---|---|---|
| 无序链表 | |||
| 最小值位于表头的有序链表 | |||
| 二叉堆 | |||
| 平衡二叉搜索树 | ,若缓存最小值则为 | ||
| 斐波那契堆 | 摊还 | 摊还 |
这些界限描述的是数据结构的主要操作。动态内存分配、数组大小调整以及用户定义的比较操作都可能带来额外开销。
当插入占主导、很少取出最小值时,无序表示很有用。有序表示则作出了相反的取舍。红黑树等平衡树还提供有序遍历和范围查询等额外能力,但通常比基于数组的堆需要更多的结构性开销。
二叉堆
二叉堆是一棵满足堆序性质的完全二叉树。在最小堆中,每个父节点的键都不大于其子节点的键。因此,根节点包含一个最小元素,但其余元素并未在全局范围内排好序。
这棵树通常存储在数组(数据结构)中。使用从零开始的索引时,索引为 的节点,其子节点位于
前提是这些位置存在。对于 ,其父节点位于
插入时,先将新元素追加到末尾;只要违反堆序,就反复将其与父节点交换。这称为上浮。
取出时,先移除根节点,将最后一个元素移到根节点的位置,再通过下沉恢复堆序,即根据需要将其与较小的子节点交换。这两个过程都沿着一条路径进行,路径长度至多与树高成正比,因此耗时为 。
使用自底向上的建堆方法,可以在 时间内将现有数组转换为堆。这比逐个插入元素所需的 最坏情况开销更低。之所以能达到线性时间,是因为大多数节点都靠近叶节点,只需少量下移,甚至无需移动。
二叉堆使用 的存储空间,布局紧凑,通常有利于 CPU 缓存局部性。
其他堆家族
多种堆的变体分别针对不同操作进行了优化:
- 叉堆允许每个节点最多有 个子节点。增大 会降低树高,但会增加向下修复时对子节点的比较次数。
- 二项堆将元素组织成一组具有特定结构的树,并支持在 时间内合并。
- 斐波那契堆支持摊还时间为 的插入、合并和减小键操作,取出最小值的摊还时间为 。
- 配对堆采用相对简单的树链接操作,是实现可合并优先队列的另一种选择。
摊还分析给出的界限约束的是一系列操作中每次操作的平均开销,并不保证每个单独操作都具有这一开销。精巧的渐近复杂度界限也不意味着在所有工作负载下都运行得更快:内存分配、指针访问、比较开销以及实现复杂度都很重要。
修改优先级与定位元素
在堆中查找最小值很高效,但查找任意元素并非如此。仅靠二叉堆本身,定位某个特定元素可能需要 时间。
索引优先队列维护从元素标识符到堆中位置的映射。每当两个堆条目交换位置时,也会更新这一映射。一旦知道元素的位置,在二叉堆中修改其优先级或删除它都只需 时间。对于稠密的标识符空间,可以使用数组建立映射;对于更一般的标识符,则可以使用哈希表。
另一种方法是惰性失效。程序不更新已有条目,而是插入新条目,并将旧条目标记为失效,或者另外记录当前版本。取出元素时,遇到失效条目就将其丢弃。这避免了专门的减小键操作,但可能增加内存消耗和取出操作的次数。
直接修改已存储元素的优先级,而不通知队列或修复其结构,可能破坏堆序。同样,如果优先级取决于时间或其他可变的外部状态,就必须保证元素间的相对次序仍然有效,否则就要更新数据结构。
应用
图搜索与最短路径
迪ijkstra算法使用最小优先队列,选择暂定距离最小的顶点。对于具有 个顶点和 条边的图,使用邻接表和索引二叉堆的实现需要
时间。若使用斐波那契堆,相应的时间界限为 。这些界限都以边权非负为前提,这也是 Dijkstra 算法的要求。
A星搜索根据估计的路径总成本为候选状态确定优先级,通常写作
其中, 是到达某个状态的已知成本, 则估计剩余成本。
优先队列也用于最小生成树算法,以及其他需要反复选择当前最优候选项的过程。
调度与事件处理
在处理器调度中,就绪任务可以按优先级、截止时间或其他调度键排序。优先队列提供的是选择机制,本身并不定义调度策略。
离散事件仿真维护一个按模拟执行时间排序的未来事件队列。仿真器反复取出最早的事件,对其进行处理,再插入新产生的事件。定时器管理和某些事件循环实现也采用类似的安排。
如果高优先级的工作持续到来,严格优先级调度可能导致饥饿。优先级老化等技术通过改变调度策略来解决这一问题;公平性并不是优先队列固有的性质。
压缩、合并与选择
霍夫曼编码反复移除权重最低的两个节点,并插入一个代表二者组合的新节点。
优先队列还可以用于合并 个有序序列,方法是在队列中维护每个序列下一个可用的元素。对于总计 个元素,除去输入输出开销,这需要 时间。
若要保留数据流中最大的 个元素,可以使用大小不超过 的最小堆,将已保留元素中最小的一个放在堆顶。这样,对于每个新候选元素,都可以决定将其丢弃,或者用它替换堆顶;这一处理可在 时间内完成。
与排序和队列的关系
反复从优先队列中取出最小值,会得到按非递减顺序排列的元素。堆排序利用堆序,实现了 的最坏情况运行时间。
基于比较的排序下界也限制了优先队列的性能。对于任意可比较的键,队列不可能在所有输入下同时提供常数摊还时间的插入和取出操作:否则,插入 个元素后再将它们全部取出,就能得到一个耗时 的基于比较的排序算法。
对于受限的键值域,这一论证不能原封不动地套用。较小的整数优先级可以用桶来处理,而专门的整数队列可以利用键的表示方式,或对其顺序的限制。
普通队列或栈(数据类型)都可以通过按到达顺序分配优先级来建模。不过,它们的专用实现通常更简单,并且对各自特定的操作更高效。
实际限制与接口细节
优先队列保证能够访问极值元素,但不保证按序迭代。遍历堆的底层数组,通常既得不到插入顺序,也得不到优先级顺序。
标准二叉堆也不支持特别高效的合并:将两个堆数组拼接后重新建堆,所需时间与二者的总大小成线性关系。经常进行合并的应用可能更适合使用可合并堆。
在并发计算中,同时进行的插入和取出操作需要协调。精确取出最小值可能成为争用热点,因为许多工作线程都在争夺排序中的同一端。一些并发设计会放宽要求,返回一个接近最小值的元素,以牺牲严格语义来换取更高的吞吐量。
最后,不同标准库接口提供的能力各不相同。某个库的优先队列可能只支持插入、查看和取出,即使其底层结构本来能够支持更多操作。稳定性、任意删除、优先级更新、线程安全以及空队列的处理方式,都是具体接口的属性,而不是所有优先队列的普遍保证。