優先佇列
优先队列（priority queue）是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用「堆積」（heap）实现。
操作
[编辑]优先队列至少需要支持下述操作：
- 插入带优先级的元素（insert_with_priority）
- 取出具有最高优先级的元素（pull_highest_priority_element）
- 查看最高优先级的元素（peek）：O(1) 时间复杂度
其它可选的操作：
- 检查优先级高的一批元素
- 清空优先队列
- 批插入一批元素
- 合并多个优先队列
- 调整一个元素的优先级
实现
[编辑]初级实现
[编辑]有许多简单低效的实现。如用一个有序的数组；或使用无序数组，在每次取出时搜索全集合，这种方法插入的效率为O(1)，但取出时效率为O(n)。
典型实现
[编辑]出于性能考虑，优先队列用堆来实现，具有O(log n)时间复杂度的插入元素性能，O(n)的初始化构造的时间复杂度。如果使用自平衡二叉查找树，插入与删除的时间复杂度为O(log n)，构造二叉树的时间复杂度为O(n log n)。
从计算复杂度的角度，优先级队列等价于排序算法。
有一些特殊的堆为优先队列的实现提供了额外的性能：二叉堆的插入与提取操作的时间复杂度为O(log n)，并可以常量时间复杂度的peek操作。二项堆提供了几种额外操作。斐波那契堆的插入、提取、修改元素优先级等操作具有分摊常量时间复杂度，[1]，但删除操作的时间复杂度为O(log n)。Brodal queue具有最糟糕情况下的常量复杂度但算法相当复杂因而不具有实用性。
对于整型、浮点型等具有有限值域的元素的数据类型，优先队列有更快的实现。
库实现
[编辑]优先队列是计算机科学中的一类"容器数据类型"。
标准模板库（STL）以及1998年的C++标准确定优先队列是标准模板库的容器适配器模板。其实现了一个需要三个参数的最大优先队列：比较函数（缺省情况是小于函数less<T>）、存储数据所用的容器类型（缺省情况是向量vector<T>）以及指向序列开始和结束位置的两个迭代器。和标准模板库中其他的真实容器不同，优先队列不允许使用其元素类型的迭代器，而必须使用优先队列抽象数据类型的迭代器。标准模板库还实现了支持随机访问数据容器的优先队列--二叉最大堆。Boost C++库也在其中实现了堆结构。
Python的heapq （页面存档备份，存于互联网档案馆）模块实现了在链表基础上的二叉最小堆，queue （页面存档备份，存于互联网档案馆）模块将heapq模块包装实现了PriorityQueue类。
Java库中的PriorityQueue类实现了最小优先队列。
Go库中的container/heap （页面存档备份，存于互联网档案馆）模块实现了一个可以在任何兼容数据结构上构建的最小堆。
PHP标准库包括了一个优先队列SplPriorityQueue （页面存档备份，存于互联网档案馆）。
苹果的Core Foundation框架包括了一个最小堆结构CFBinaryHeap （页面存档备份，存于互联网档案馆）。
应用
[编辑]优先队列常用于操作系统的任务调度，也是贪心算法的重要组成部分。[2]
参考文献
[编辑]- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 20: Fibonacci Heaps, pp.476–497. Third edition p518.
- ^ Mikkel Thorup. On RAM priority queues. Proceeding SODA '96 Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms. 1996: 59–67 [2019-09-11].