優先佇列
優先隊列（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].