优先队列

✍ dations ◷ 2025-06-08 12:45:34 #数据结构

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

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

其它可选的操作:

有许多简单低效的实现。如用一个有序的数组;或使用无序数组,在每次取出时搜索全集合,这种方法插入的效率为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。

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

相关

  • 胸腺细胞胸腺细胞(Thymocyte)是位于胸腺皮质中的细胞。胸腺细胞主要为处于不同分化状态的成熟T细胞,其与胸腺基质细胞(thymic stromal cell,TSC)组成了胸腺微环境。 其主要位于皮质上皮细
  • 隆都话广东省中山市沙溪、大涌、南蓢、三乡及火炬开发区等地;中山闽语是汉藏语系汉语族闽语支闽南语在广东省境内的一种方言,通行于古香山县之隆都、得能都、四大都、谷都和恭常都等
  • 奥地利银行奥地利银行(UniCredit Bank Austria AG,常称:Bank Austria)是裕信银行其下主要负责中东欧业务的银行。成立于1991年。自2007年起开始负责欧盟所有裕信银行旗下业务。
  • 二部二部,是为汉字索引中的部首之一,康熙字典214个部首的第七个(二划的则为第一个)。繁体中文中,二部归于二划部首。二部通常从上方、下方为部字,且无其他部首可用者将部首归为二部,中
  • 美国普查局美国普查局(英语:United States Census Bureau,按《美国法典第13卷 § 11》官方称呼为Bureau of the Census)是美国商务部经济和统计管理局下属的一个机关。它的任务由美国宪
  • 同源框蛋白质NANOGn/an/an/an/an/an/an/an/an/an/aNANOG(读法:nanOg)是一种对未分化的胚胎干细胞(ESC)自我更新至关重要的转录因子。人体的NANOG蛋白质由基因编码。人类NANOG蛋白质是一种长305氨酸
  • 绿党/欧洲自由联盟绿党/欧洲自由联盟(英语:The Greens/European Free Alliance,缩写为Greens/EFA;法语:Groupe des Verts/Alliance libre européenne,缩写为Verts/ALE)是欧洲议会中的一个党团, 由欧
  • 段彩华段彩华(1933年1月18日-2015年1月13日),原籍江苏宿迁,台湾小说家。段彩华毕业于徐州建国中学、革命实践研究学院大众传播系。1949年在长沙从军,旋即随军来到台湾,于1962年退役。曾任
  • 贵族 (歌曲)《贵族》(英语:Royals)是新西兰歌手萝儿的一首歌曲,出自她2012年的首张迷你专辑《爱情俱乐部》(),随后收录于她2013年的首张录音室专辑《纯粹女英雄》()。歌曲融合了艺术摇滚、流行电
  • 冰巨行星冰巨行星(英语:ice giant、类海行星),是一种主要由比氢和氦更重的气体组成的巨行星,例如氧,碳,氮,和硫。在太阳系里,天王星和海王星均是典型的冰巨行星。它们的质量包括约20%的氢和氦