優先佇列

维基百科,自由的百科全书
跳转至: 导航搜索

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

操作[编辑]

优先队列起码支持下述操作:

  • 插入带优先级的元素(insert_with_priority)
  • 取出具有最高优先级的元素(pull_highest_priority_element)
  • 查看最高优先级的元素(peek):O(1)时间复杂度。

其它可选的操作:

  • 检查优先级高的一批元素
  • 清空优先队列
  • 批插入一批元素
  • 合并多个优先队列
  • 调整一个元素的优先级

实现[编辑]

Naive实现[编辑]

如用一个有序的数据结构;或者使用一个集合,每次取出具有最高优先级的元素时搜索全集合。

典型实现[编辑]

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

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

有一些特殊的为优先队列的实现提供了额外的性能:二叉堆的插入与提取操作的时间复杂度为 O(log n),并可以常量时间复杂度的peek操作。二项堆提供了几种额外操作。斐波那契堆的插入、提取、修改元素优先级等操作具有分摊常量时间复杂度,[1],但删除操作的时间复杂度为O(log n)。Brodal queue英语Brodal queue具有最糟糕情况下的常量复杂度但算法相当复杂因而不具有实用性。

对于整型、浮点型等具有有限值域的元素的数据类型,优先队列有更快的实现。

库实现[编辑]

优先队列是计算机科学中的一类"容器数据类型"。

参考文献[编辑]

  1. ^ 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.