下面是關于 C++ 中 std::priority_queue 的詳細說明，包括初始化、用法和常見的應用場景。
什么是 priority_queue？
priority_queue（優先隊列）是 C++ 標準庫中的一個容器適配器。它和普通隊列（queue）最大的不同在于，元素的出隊順序不是根據它們入隊的順序（先進先出），而是根據它們的優先級。
默認情況下，priority_queue 是一個大頂堆（Max-Heap），意味著優先級最高的元素是值最大的元素。每次調用 top() 都會返回當前隊列中最大的元素。
- 底層實現：通常使用**堆（Heap）**數據結構來實現，這使得它能以對數時間復雜度（O(log n)）插入元素和刪除最大（或最小）的元素。
- 頭文件：使用前需要包含頭文件
<queue>。
#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 包含 std::greater 和 std::less
1. priority_queue 的初始化
priority_queue 的模板定義如下：
template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>>
class priority_queue;
T: 存儲的元素類型。Container: 用于存儲元素的底層容器，默認為std::vector<T>。必須是支持隨機訪問迭代器和front(),push_back(),pop_back()等操作的序列容器，例如std::vector和std::deque。Compare: 比較函數或函數對象，用于確定元素的優先級。默認為std::less<T>，它會創建一個大頂堆。
1.1 默認初始化（大頂堆）
最常見的用法，創建一個存儲 int 類型的大頂堆。每次 top() 都會返回最大的元素。
// 默認情況下，是 std::vector 作為容器，std::less 作為比較函數，即大頂堆
std::priority_queue<int> max_heap;max_heap.push(30);
max_heap.push(100);
max_heap.push(25);
max_heap.push(40);// 此刻隊列頂部的元素是 100
std::cout << "Top element is: " << max_heap.top() << std::endl; // 輸出 100
1.2 初始化為小頂堆
如果你想讓 top() 總是返回最小的元素，你需要創建一個小頂堆（Min-Heap）。這需要顯式提供所有模板參數：
T: 元素類型。Container: 底層容器，通常是std::vector<T>。Compare: 比較函數，使用std::greater<T>。
// 使用 std::greater<int> 來創建小頂堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;min_heap.push(30);
min_heap.push(100);
min_heap.push(25);
min_heap.push(40);// 此刻隊列頂部的元素是 25
std::cout << "Top element is: " << min_heap.top() << std::endl; // 輸出 25
1.3 存儲自定義結構體
當存儲自定義類型（如 struct 或 class）時，你需要告訴優先隊列如何比較它們。有兩種主要方法：
方法一：重載 < 運算符（用于大頂堆）
struct Node {int id;int priority;// 重載 < 運算符，priority 越大，優先級越高bool operator<(const Node& other) const {return this->priority < other.priority;}
};std::priority_queue<Node> pq;
pq.push({1, 10});
pq.push({2, 5});
pq.push({3, 20});// top() 將返回 priority 最大的 Node，即 {3, 20}
std::cout << "Top node: id=" << pq.top().id << ", priority=" << pq.top().priority << std::endl;
方法二：提供自定義比較器（更靈活）
如果你不想或不能修改結構體定義，或者需要多種排序方式，可以提供一個自定義的比較函數對象（Functor）。
struct Node {int id;int priority;
};// 自定義比較器結構體
struct CompareNode {// 返回 true 表示 a 的優先級低于 bbool operator()(const Node& a, const Node& b) {// 創建小頂堆，priority 越小，優先級越高return a.priority > b.priority;}
};std::priority_queue<Node, std::vector<Node>, CompareNode> pq;
pq.push({1, 10});
pq.push({2, 5});
pq.push({3, 20});// top() 將返回 priority 最小的 Node，即 {2, 5}
std::cout << "Top node: id=" << pq.top().id << ", priority=" << pq.top().priority << std::endl;
使用 Lambda 表達式（C++11及以上）也可以實現，但定義比較器時需要 decltype。
1.4 從已有容器初始化
你可以用一個已有的容器（如 vector）中的元素來初始化優先隊列。
std::vector<int> data = {30, 100, 25, 40};// 從 data 初始化一個大頂堆
std::priority_queue<int> max_heap_from_vec(data.begin(), data.end());std::cout << "Top element from vector init: " << max_heap_from_vec.top() << std::endl; // 輸出 100// 初始化小頂堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap_from_vec(data.begin(), data.end());
std::cout << "Top element from vector init (min-heap): " << min_heap_from_vec.top() << std::endl; // 輸出 25
2. priority_queue 的常用操作
優先隊列的操作非常簡單直觀：
push(element): 向隊列中插入一個元素。時間復雜度 O(log n)。pop(): 移除隊首（優先級最高）的元素。時間復雜度 O(log n)。top(): 返回隊首（優先級最高）元素的常引用，不刪除元素。時間復雜度 O(1)。empty(): 檢查隊列是否為空。size(): 返回隊列中元素的數量。
示例代碼：
std::priority_queue<int> pq;std::cout << "Is queue empty? " << (pq.empty() ? "Yes" : "No") << std::endl;pq.push(10);
pq.push(50);
pq.push(20);std::cout << "Queue size: " << pq.size() << std::endl;
std::cout << "Top element: " << pq.top() << std::endl; // 50pq.pop(); // 移除了 50std::cout << "Top element after pop: " << pq.top() << std::endl; // 20// 遍歷并清空優先隊列
std::cout << "Queue elements in priority order: ";
while (!pq.empty()) {std::cout << pq.top() << " ";pq.pop();
}
std::cout << std::endl;
// 輸出: Queue elements in priority order: 20 10
注意：priority_queue 沒有提供迭代器，不能像 vector 那樣直接遍歷。唯一的訪問方式就是通過 top() 獲取隊首元素。
3. priority_queue 的應用場景
優先隊列在算法和系統設計中非常有用，尤其適合處理那些需要動態維護“最大/最小”元素的問題。
3.1 Top-K 問題
這是最經典的應用。例如，從一個巨大的數據流中找出最大的 K 個元素。
思路：
- 維護一個大小為 K 的小頂堆。
- 遍歷數據流，對于每個新元素：
- 如果堆的大小小于 K，直接將元素插入堆中。
- 如果堆的大小等于 K，將新元素與堆頂元素（當前 K 個元素中最小的那個）比較。
- 如果新元素大于堆頂元素，則彈出堆頂，并將新元素插入。
- 遍歷結束后，堆中剩下的 K 個元素就是最大的 K 個元素。
為什么用小頂堆？ 因為小頂堆的堆頂是“門檻”，只有比這個門檻大的元素才有資格進入這個“Top-K 圈子”，這樣可以高效地淘汰掉不夠大的元素。
3.2 堆排序（Heap Sort）
雖然 C++ 提供了 std::sort，但優先隊列可以很自然地實現堆排序。
- 將所有元素插入一個大頂堆。
- 依次從堆中取出堆頂元素，放入結果數組中。取出的順序就是從大到小。
3.3 Dijkstra 算法
在圖論中，Dijkstra 算法用于尋找圖中單源最短路徑。算法的核心是每次都從“待處理”的頂點中，選擇一個距離源點最近的頂點進行擴展。優先隊列（小頂堆）可以完美地勝任這個任務。
- 優先隊列中存儲
pair<int, int>，即{距離, 頂點編號}。 - 每次從隊列中取出
top()，就是當前距離源點最近的未訪問頂點。
3.4 Huffman 編碼
在數據壓縮中，Huffman 編碼算法使用優先隊列來構建最優二叉樹（Huffman 樹）。
- 將每個字符及其頻率作為一個節點放入一個優先隊列（小頂堆）中，頻率越小，優先級越高。
- 每次從隊列中取出兩個頻率最小的節點，合并成一個新的父節點（頻率為兩者之和），再將新節點放回優先隊列。
- 重復此過程，直到隊列中只剩一個節點，即 Huffman 樹的根。
3.5 任務調度系統
在操作系統或中間件中，任務調度器需要從多個待執行的任務中選擇一個優先級最高的來執行。優先隊列可以用來管理這些任務，top() 總是返回當前最緊急的任務。
希望這份詳細的說明對你有幫助！
