Priority queue
优先队列（Priority Queue）是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用堆（Heap）实现。
复杂度¶
- 获取堆顶元素 \(O(1)\)
- 入队 \(O(log{}N)\)
- 出队 \(O(log{}N)\)
- 检测是否为空 \(O(1)\)
- 获取元素个数 \(O(1)\)
不能轻易删除某个特定元素，有需求请使用 multiset。
简单使用¶
使用 priority_queue 需要包含头文件 #include <queue>。
// 默认参数
priority_queue<int> pq1;
// 默认使用 vector 作为容器
priority_queue<int, vector<int>> pq2;
// 默认使用 less 比较函数，堆顶元素最大 [大顶堆]
priority_queue<int, vector<int>, less<int>> pq3;
print_pq(pq3); // 3 2 1
// greater 比较函数，堆顶元素最小 [小顶堆]
priority_queue<int, vector<int>, greater<int>> pq4;
print_pq(pq4); // 1 2 3
对于简单类型的Compare，less 表示从堆顶元素开始依次变小，堆顶为最大，因此使用less的priority_queue为大顶堆。反之，greater表示小顶堆。
priority_queue<int> pq1;
pq1.push(1);
pq1.pop();
pq1.top();
// C++23
// 插入一系列元素并对底层容器进行排序
// 插入每个元素的副本
pq1.push_range({1,2,3});
priority_queue<pair<string, int>> pq2;
// C++11
pq2.emplace("abc", 1);
自定义比较函数¶
auto compare = [](auto& a, auto& b) { return a.second < b.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> pq(compare);
priority_queue<pair<int, int>, vector<pair<int, int>>, auto(*)(pair<int, int>,pair<int, int>)->bool> pq([](pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
});