C++中的priority_queue容器使用及說明
更新時間：2026年04月10日 08:51:01 作者：你的冰西瓜
文章主要介紹了C++標準模板庫中的優(yōu)先級隊列(priority_queue)的功能、實現(xiàn)原理、使用方法及應用場景,優(yōu)先級隊列提供按優(yōu)先級排序的數(shù)據(jù)存儲方式,默認為最大堆實現(xiàn),通過分析其構(gòu)造函數(shù)、操作函數(shù)、性能考慮等內(nèi)容,展示了優(yōu)先級隊列在實際應用中的優(yōu)勢與注意事項
1.priority_queue概述
priority_queue是C++標準模板庫(STL)中的容器適配器，提供優(yōu)先級隊列功能。它保證優(yōu)先級最高的元素總是位于隊列前端，默認情況下是最大堆實現(xiàn)（最大元素優(yōu)先）。
2. 基本特性
- 優(yōu)先級排序：元素按優(yōu)先級排序，默認最大元素在前
- 容器適配器：基于其他序列容器實現(xiàn)（默認
vector） - 限制訪問：只允許訪問頂部元素
- 高效操作：插入和刪除操作時間復雜度為O(log?2n)O(\log_2 n)O(log2?n)
- 堆結(jié)構(gòu)：底層使用堆數(shù)據(jù)結(jié)構(gòu)實現(xiàn)
3. 頭文件與聲明
#include <queue> // 注意：priority_queue也在<queue>頭文件中 using namespace std; priority_queue<int> pq1; // 默認最大堆，基于vector priority_queue<int, vector<int>, greater<int>> pq2; // 最小堆 priority_queue<string> pq3;
4. 構(gòu)造函數(shù)與初始化
4.1 默認構(gòu)造
priority_queue<int> pq; // 創(chuàng)建空的最大堆
4.2 基于比較函數(shù)構(gòu)造
// 自定義比較函數(shù)
struct Compare {
bool operator()(int a, int b) {
return a > b; // 最小堆
}
};
priority_queue<int, vector<int>, Compare> custom_pq;
4.3 使用已有數(shù)據(jù)初始化
vector<int> vec = {3, 1, 4, 1, 5};
priority_queue<int> pq(vec.begin(), vec.end()); // 使用迭代器范圍構(gòu)造
5. 容量操作
5.1empty()
if (pq.empty()) {
cout << "優(yōu)先級隊列為空";
}
5.2size()
cout << "優(yōu)先級隊列大小: " << pq.size();
6. 元素訪問
6.1top()
if (!pq.empty()) {
cout << "最高優(yōu)先級元素: " << pq.top();
}
7. 修改操作
7.1push()
pq.push(10); // 插入元素 pq.push(20); pq.push(5);
7.2emplace()
pq.emplace(15); // 原地構(gòu)造元素(避免拷貝)
7.3pop()
if (!pq.empty()) {
pq.pop(); // 移除最高優(yōu)先級元素
}
7.4swap()(C++11)
priority_queue<int> pq2; pq.swap(pq2); // 交換兩個優(yōu)先級隊列
8. 完整示例
#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 用于greater<int>
using namespace std;
int main() {
// 最大堆示例
priority_queue<int> max_heap;
max_heap.push(30);
max_heap.push(10);
max_heap.push(50);
max_heap.emplace(20);
cout << "最大堆元素: ";
while (!max_heap.empty()) {
cout << max_heap.top() << " ";
max_heap.pop();
}
cout << endl;
// 最小堆示例
priority_queue<int, vector<int>, greater<int>> min_heap;
min_heap.push(30);
min_heap.push(10);
min_heap.push(50);
min_heap.emplace(20);
cout << "最小堆元素: ";
while (!min_heap.empty()) {
cout << min_heap.top() << " ";
min_heap.pop();
}
cout << endl;
// 自定義比較函數(shù)示例
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
bool operator<(const Point& other) const {
return (x*x + y*y) < (other.x*other.x + other.y*other.y);
}
};
priority_queue<Point> point_pq;
point_pq.emplace(1, 2);
point_pq.emplace(3, 4);
point_pq.emplace(0, 1);
cout << "按與原點的距離排序的點: ";
while (!point_pq.empty()) {
Point p = point_pq.top();
cout << "(" << p.x << "," << p.y << ") ";
point_pq.pop();
}
cout << endl;
return 0;
}
9. 底層容器與比較函數(shù)
9.1 底層容器選擇
priority_queue可以基于以下容器實現(xiàn)：
vector（默認）：隨機訪問性能好，適合堆操作deque：兩端操作高效，但內(nèi)存使用不如vector緊湊
9.2 比較函數(shù)
less<T>（默認）：最大堆，大元素優(yōu)先greater<T>：最小堆，小元素優(yōu)先- 自定義比較函數(shù)：實現(xiàn)復雜排序邏輯
// 自定義比較函數(shù)示例：按字符串長度排序
struct LengthCompare {
bool operator()(const string& a, const string& b) {
return a.length() < b.length(); // 長度大的優(yōu)先
}
};
priority_queue<string, vector<string>, LengthCompare> length_pq;
10. 實際應用示例
10.1 合并KKK個有序鏈表
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
struct CompareNode {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; // 最小堆
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, CompareNode> pq;
for (auto node : lists) {
if (node) pq.push(node);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
tail->next = pq.top();
pq.pop();
tail = tail->next;
if (tail->next) {
pq.push(tail->next);
}
}
return dummy.next;
}
10.2 查找前KKK個高頻元素
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (auto& [num, count] : freq) {
pq.push({count, num});
if (pq.size() > k) {
pq.pop();
}
}
vector<int> result;
while (!pq.empty()) {
result.push_back(pq.top().second);
pq.pop();
}
return result;
}
11. 性能考慮
時間復雜度：
push(): O(log?2n)O(\log_2 n)O(log2?n)pop(): O(log?2n)O(\log_2 n)O(log2?n)top(): O(1)O(1)O(1)empty(): O(1)O(1)O(1)size(): O(1)O(1)O(1)
空間復雜度：O(n)O(n)O(n)
底層容器選擇影響：
vector：內(nèi)存局部性好，通常性能更優(yōu)deque：在某些情況下可能提供更好的性能
12. 注意事項
- 調(diào)用
top()或pop()前必須檢查隊列是否為空 priority_queue不提供迭代器，無法遍歷內(nèi)部元素- 自定義比較函數(shù)需要嚴格弱序
- 默認是最大堆，要創(chuàng)建最小堆需要顯式指定
greater<T>
13. priority_queue與其他容器比較
| 特性 | priority_queue | queue | set |
|---|---|---|---|
| 排序方式 | 按優(yōu)先級 | FIFO | 按鍵值排序 |
| 訪問方式 | 僅頂部元素 | 隊首和隊尾 | 任意元素 |
| 插入復雜度 | O(log?2n)O(\log_2 n)O(log2?n) | O(1)O(1)O(1) | O(log?2n)O(\log_2 n)O(log2?n) |
| 刪除復雜度 | O(log?2n)O(\log_2 n)O(log2?n) | O(1)O(1)O(1) | O(log?2n)O(\log_2 n)O(log2?n) |
| 重復元素 | 允許 | 允許 | 不允許 |
總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
今天我要跟大家介紹二叉搜索樹中的另一顆樹——紅黑樹，它主要是通過控制顏色來控制自身的平衡，但它的平衡沒有AVL樹的平衡那么嚴格2022-06-06
本文主要介紹了淺談QT打包的兩種方式，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
socketpair()創(chuàng)建已連接的匿名Unix套接字對,用于高效進程間通信,無需綁定或連接,支持雙向流式/數(shù)據(jù)報通信,適用于父子進程和線程,相比管道,提供全雙工能力,結(jié)合了易用性與靈活性,本文給大家介紹c++中socketpair函數(shù)示例,感興趣的朋友一起看看吧2025-07-07
這篇文章主要介紹了C語言遞歸實現(xiàn)字符串逆序的方式詳解,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-10-10
C語言使用普通循環(huán)方法和遞歸求斐波那契序列示例代碼
這篇文章主要介紹了C語言使用普通循環(huán)方法和遞歸求斐波那契序列示例代碼,大家參考使用吧2013-11-11
本文主要介紹了C語言malloc與calloc區(qū)別詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易版三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要為大家詳細介紹了OpenCV獲取鼠標左鍵點擊位置圖像的像素值，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
Qt圖形圖像開發(fā)之曲線圖表模塊QChart庫坐標軸和數(shù)據(jù)不對應、密集的散點圖無法顯示問題解決方法
這篇文章主要介紹了Qt圖形圖像開發(fā)之曲線圖表模塊QChart庫坐標軸和數(shù)據(jù)不對應、密集的散點圖無法顯示問題解決方法,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了c語言實現(xiàn)計算圓周率的近似值方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12