優先佇列

優先隊列（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操作。二項堆提供了幾種額外操作。斐波那契堆的插入、提取、修改元素優先級等操作具有分攤常量時間複雜度，，但刪除操作的時間複雜度為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 （頁面存檔備份，存於網際網路檔案館）。

應用

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