優先佇列

電腦科學中的抽象資料類型

優先隊列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英語Brodal queue具有最糟糕情況下的常量複雜度但算法相當複雜因而不具有實用性。

對於整型、浮點型等具有有限值域的元素的數據類型,優先隊列有更快的實現。

庫實現

優先隊列是計算機科學中的一類"容器數據類型"。

標準模板庫(STL)以及1998年的C++標準確定優先隊列是標準模板庫的容器適配器模板。其實現了一個需要三個參數的最大優先隊列:比較函數(缺省情況是小於函數less<T>)、存儲數據所用的容器類型(缺省情況是向量vector<T>)以及指向序列開始和結束位置的兩個迭代器。和標準模板庫中其他的真實容器不同,優先隊列不允許使用其元素類型的迭代器,而必須使用優先隊列抽象數據類型的迭代器。標準模板庫還實現了支持隨機訪問數據容器的優先隊列--二叉最大Boost C++庫也在其中實現了堆結構。

Pythonheapq頁面存檔備份,存於網際網路檔案館)模塊實現了在鍊表基礎上的二叉最小堆,queue頁面存檔備份,存於網際網路檔案館)模塊將heapq模塊包裝實現了PriorityQueue類別。

Java庫中的PriorityQueue類別實現了最小優先隊列。

Go庫中的container/heap頁面存檔備份,存於網際網路檔案館)模塊實現了一個可以在任何兼容數據結構上構建的最小堆。

PHP標準庫包括了一個優先隊列SplPriorityQueue頁面存檔備份,存於網際網路檔案館)。

蘋果Core Foundation框架包括了一個最小堆結構CFBinaryHeap頁面存檔備份,存於網際網路檔案館)。

應用

優先隊列常用於操作系統的任務調度,也是貪心算法的重要組成部分。[2]

參考文獻

  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.
  2. ^ 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].