优先队列

✍ dations ◷ 2025-06-30 02:52:00 #数据结构

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

优先队列至少需要支持下述操作:

其它可选的操作:

有许多简单低效的实现。如用一个有序的数组;或使用无序数组,在每次取出时搜索全集合,这种方法插入的效率为O(1),但取出时效率为​O(n)。

出于性能考虑,优先队列用堆来实现,具有(log )时间复杂度的插入元素性能,()的初始化构造的时间复杂度。如果使用自平衡二叉查找树,插入与删除的时间复杂度为(log ),构造二叉树的时间复杂度为( log )。

从计算复杂度的角度,优先级队列等价于排序算法。

有一些特殊的堆为优先队列的实现提供了额外的性能:二叉堆的插入与提取操作的时间复杂度为(log ),并可以常量时间复杂度的peek操作。二项堆提供了几种额外操作。斐波那契堆的插入、提取、修改元素优先级等操作具有分摊常量时间复杂度,,但删除操作的时间复杂度为(log )。Brodal queue(英语: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。

优先队列常用于操作系统的任务调度,也是贪心算法的重要组成部分。

相关

  • 广亩城市广亩城市(英语:Broadacre City)是由建筑师弗兰克·劳埃德·赖特在其1932年出版的著作《正在消灭中的城市》(The Disappearing City)中提出的一个城市规划概念构想。他认为现代的
  • 先进先出财务会计 · 管理会计 ·先进先出法(英语:First In, First Out,FIFO)是一种存货记账方法,假设用于再加工、出售的原材料或产品存货是最早购入的存货,以最早购入的存货成本作为损
  • 宿雾市宿务市(宿务语:Dakbayan sa Sugbo;英文:Cebu City)是菲律宾宿务省的首府,也是菲律宾第二大城。宿务市位于宿务岛东南岸,是首都马尼拉也无法比拟的菲律宾历史悠久之城。由于位处菲律
  • 郭显德郭显德 (Hunter Corbett,1835年12月8日-1920年1月7日),出生于美国宾夕法尼亚州,美北长老会传教士。在中国山东度过了56年,步行千里,下乡布道与苦力贫民同眠共食,又广行善事。一生施
  • 诊断 (工程)诊断是指找出一特定现象的本质及产生原因,再配合逻辑、分析及经验来判断因果关系,在许多不同的领域都有用到诊断,像医疗诊断即为诊断的一种。在系统工程及计算机科学中,会用诊断
  • 兰炭鳄属兰炭鳄属(学名:)是副爬行动物的一属,生存于二叠纪晚期的俄罗斯鞑靼斯坦,完整身长估计约75公分。
  • 直到雨停的那一天《直到雨停的那一天》(日语:いつかこのあめがやむひまで,英语:Juliet In The Rain))是由日本东海电视台制作的电视剧,2018年8月4日至9月29日于富士电视台大人的六剧时段播出,由渡边
  • Lol live tour 2018 -scream-‘’是日本唱跳团体lol在2019年1月30日发售的影像作品。
  • 侧线 (铁路)侧线(Siding),在铁路工程是指从道岔引出的侧向铁道,一般与正线相对。侧线是此类线路的统称,包括到发线、越行线、机走线等。客运站 · 货运站 · 编组站 · (到达场 · 编组场
  • 依兰陨石坑坐标:46°23′03″N 129°18′40″E / 46.38417°N 129.31111°E / 46.38417; 129.31111依兰陨石坑是位于中国黑龙江省哈尔滨市依兰县的陨石坑,由中国科学院广州地球化学研究