樹與層次結構

優先佇列

優先佇列是一種抽象資料型別——它描述的是行為，而不是某種具體的儲存佈局。普通佇列按先進先出的順序處理元素；優先佇列則總是優先處理優先級最高的那個元素，無論它何時到達。想想急診室：最危急的病人先被診治，而不是最早走進門的那位。

它的介面很小：按優先級壓入一個元素，再彈出（或查看）當前最緊急的那個。由於這正是堆積所擅長的形狀，優先佇列幾乎總是用二元堆積實作，於是壓入和彈出都是 O(log n)，查看是 O(1)。它也可以用別的結構支撐——有序陣列、平衡樹——但堆積是標準選擇，因為它快且不需要指標。

把這個抽象資料型別與支撐它的堆積分開，正是要點所在：你只針對「把當前最緊急的元素給我」來編程，讓函式庫去挑選底層結構。在 C++ 中就是 std::priority_queue，預設是最大堆。優先佇列是 Dijkstra 最短路、Prim 最小生成樹、事件驅動模擬和 Huffman 編碼背後的引擎——凡是你需要反覆取出當前最優或最小者的地方都用得上。

std::priority_queue<int> pq;   // max-heap by default
pq.push(3);
pq.push(9);
pq.push(5);
while (!pq.empty()) {
  std::cout << pq.top() << ' ';  // prints 9 5 3
  pq.pop();
}

std::priority_queue——披著佇列介面的最大堆。

C++ 的 std::priority_queue 預設是最大堆；傳入 std::greater（或對鍵取反）即可得到最小優先佇列。

又稱

PQ优先级队列优先权队列優先權佇列

另見

堆積佇列抽象資料型別最短路徑

← 全部術語