C++中std::priority_queue的使用小結
更新時間：2025年04月07日 08:37:03 作者：點云SLAM
std::priority_queue是C++ STL提供的優(yōu)先隊列,本文主要介紹了C++中std::priority_queue的使用小結,具有一定的參考價值,感興趣的可以了解一下
std::priority_queue 是 C++ STL 提供的 優(yōu)先隊列，它是一種 最大堆（默認情況下），可以用于高效地獲取當前最大（或最小）的元素。
1. 基本用法
(1) 頭文件
要使用 std::priority_queue，需要包含：
#include <queue> #include <vector> #include <iostream>
(2) 默認情況（最大堆）
默認情況下，std::priority_queue 是 最大堆，即 堆頂是最大元素：
std::priority_queue<int> pq; // 默認是最大堆
示例：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "堆頂元素：" << pq.top() << std::endl; // 輸出 30
pq.pop(); // 移除 30
std::cout << "新的堆頂：" << pq.top() << std::endl; // 輸出 20
return 0;
}
? 特點
push()插入元素，自動維護最大堆。top()獲取當前最大元素（堆頂）。pop()移除堆頂元素（但不返回它）。size()獲取隊列大小。empty()檢查隊列是否為空。
2. 自定義最小堆
如果要實現(xiàn) 最小堆（堆頂是最小元素），可以用 std::greater<T>：
std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
示例：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
pq_min.push(10);
pq_min.push(30);
pq_min.push(20);
std::cout << "堆頂元素：" << pq_min.top() << std::endl; // 輸出 10
pq_min.pop();
std::cout << "新的堆頂：" << pq_min.top() << std::endl; // 輸出 20
return 0;
}
? 重點
std::greater<int>使priority_queue變成 最小堆。
3. 自定義比較函數(shù)（結構體/仿函數(shù)）
(1) 結構體仿函數(shù)
struct Compare {
bool operator()(int a, int b) {
return a > b; // 最小堆（a > b 表示 a 在 b 下面）
}
};
std::priority_queue<int, std::vector<int>, Compare> pq;
示例：
#include <iostream>
#include <queue>
struct Compare {
bool operator()(int a, int b) {
return a > b; // 讓小的元素優(yōu)先級高
}
};
int main() {
std::priority_queue<int, std::vector<int>, Compare> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "堆頂元素：" << pq.top() << std::endl; // 輸出 10
pq.pop();
std::cout << "新的堆頂：" << pq.top() << std::endl; // 輸出 20
return 0;
}
? 優(yōu)點
- 適用于復雜的數(shù)據(jù)結構（如
struct）。 - 允許靈活定義優(yōu)先級。
4. 處理結構體類型
如果 priority_queue 存儲的是 自定義結構體，需要提供比較規(guī)則。
(1) 按權重排序的任務調(diào)度
#include <iostream>
#include <queue>
struct Task {
int id;
int priority;
// 重載運算符，用于最大堆（優(yōu)先級大的優(yōu)先）
bool operator<(const Task& other) const {
return priority < other.priority; // 優(yōu)先級高的排前面
}
};
int main() {
std::priority_queue<Task> pq;
pq.push({1, 3});
pq.push({2, 5});
pq.push({3, 1});
std::cout << "最高優(yōu)先級任務 ID：" << pq.top().id << std::endl; // 輸出 2
pq.pop();
std::cout << "新的最高優(yōu)先級任務 ID：" << pq.top().id << std::endl; // 輸出 1
return 0;
}
? 特點
- 默認是最大堆，因此
operator<定義為 優(yōu)先級小的在下面。
(2) 使用自定義比較函數(shù)
如果不能修改 struct，可以使用 外部比較函數(shù)：
struct CompareTask {
bool operator()(const Task& a, const Task& b) {
return a.priority > b.priority; // 最小堆
}
};
std::priority_queue<Task, std::vector<Task>, CompareTask> pq;
完整示例：
#include <iostream>
#include <queue>
struct Task {
int id;
int priority;
};
// 使 priority_queue 變成最小堆
struct CompareTask {
bool operator()(const Task& a, const Task& b) {
return a.priority > b.priority; // 小優(yōu)先級的任務優(yōu)先
}
};
int main() {
std::priority_queue<Task, std::vector<Task>, CompareTask> pq;
pq.push({1, 3});
pq.push({2, 5});
pq.push({3, 1});
std::cout << "最高優(yōu)先級任務 ID：" << pq.top().id << std::endl; // 輸出 3
pq.pop();
std::cout << "新的最高優(yōu)先級任務 ID：" << pq.top().id << std::endl; // 輸出 1
return 0;
}
? 適用場景
- 優(yōu)先隊列調(diào)度算法
- 事件驅動仿真
- A 搜索（最短路徑算法）*
5. priority_queue 適用場景
| 應用場景 | 用法 |
|---|---|
| 最大堆（默認） | std::priority_queue<int> |
| 最小堆 | std::priority_queue<int, std::vector<int>, std::greater<int>> |
| 存儲結構體（最大堆） | 結構體重載 < |
| 存儲結構體（最小堆） | std::greater<> 或自定義 Compare |
| K 大/小元素 | 維護大小為 K 的堆 |
| Dijkstra / A 搜索* | 結合 std::pair<int, int> 進行路徑計算 |
6. 經(jīng)典應用示例
(1) 找到前 K 個最大元素
#include <iostream>
#include <queue>
#include <vector>
void findTopK(std::vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 最小堆
for (int num : nums) {
pq.push(num);
if (pq.size() > k) pq.pop(); // 只保留 k 個最大值
}
std::cout << "前 " << k << " 個最大元素：" << pq.top() << std::endl;
}
int main() {
std::vector<int> nums = {3, 1, 5, 12, 2, 11};
findTopK(nums, 3); // 輸出 5
}
? 復雜度：O(N log K)
總結
std::priority_queue默認是 最大堆，可以用std::greater<>實現(xiàn) 最小堆。- 存儲結構體時，可以使用 重載
<運算符 或 自定義比較器。 - 適用于 任務調(diào)度、路徑搜索（Dijkstra/A）等場景*。
到此這篇關于C++中std::priority_queue的使用小結的文章就介紹到這了,更多相關C++ std::priority_queue的使用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++自定義函數(shù)判斷某年某月某日是這一年中第幾天的方法,涉及C++日期與時間操作相關技巧,需要的朋友可以參考下2016-06-06
本文主要介紹了Qt項目打包的實現(xiàn)步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
通常靜態(tài)數(shù)據(jù)成員在類聲明中聲明,在包含類方法的文件中初始化.初始化時使用作用域操作符來指出靜態(tài)成員所屬的類.但如果靜態(tài)成員是整型或是枚舉型const,則可以在類聲明中初始化2013-09-09
這篇文章主要介紹了C語言 sizeof 函數(shù)，在 C 語言中，char 字符串也是一種非常重要的數(shù)據(jù)類型，我們除了使用 sizeof 函數(shù)獲取字符串長度之外，使用 sizeof 函數(shù)同樣也可以完成字符串長度的獲取，下面文章內(nèi)容具體描述該內(nèi)容,需要的朋友可以參考以下2021-10-10
本文主要介紹了C語言中限制鏈表的長度,通過在添加新元素時檢查鏈表的當前長度是否已經(jīng)達到預設的最大值來實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2025-03-03
C語言中怎么在main函數(shù)開始前執(zhí)行函數(shù)
C語言中怎么在main函數(shù)開始前執(zhí)行函數(shù)呢？下面小編就大家詳細的介紹一下。需要的朋友可以過來參考下，希望對大家有所幫助2013-10-10
本文將會介紹如何使用模板以及參數(shù)生成器來批量生成測試用例，簡化繁瑣的性能測試代碼2021-06-06
這篇文章主要為大家詳細介紹了C語言實現(xiàn)UDP通信，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要為大家詳細介紹了C語言三個函數(shù)的模擬實現(xiàn)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
以下是對c#中WebBrowser控件的使用方法進行了詳細的分析介紹，需要的朋友參考下2013-07-07