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