我要评论1.priority_queue概述
priority_queue是c++标准模板库(stl)中的容器适配器，提供优先级队列功能。它保证优先级最高的元素总是位于队列前端，默认情况下是最大堆实现（最大元素优先）。
2. 基本特性
- 优先级排序：元素按优先级排序，默认最大元素在前
- 容器适配器：基于其他序列容器实现（默认
vector） - 限制访问：只允许访问顶部元素
- 高效操作：插入和删除操作时间复杂度为o(log2n)o(\log_2 n)o(log2n)
- 堆结构：底层使用堆数据结构实现
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. 构造函数与初始化
4.1 默认构造
priority_queue<int> pq; // 创建空的最大堆
4.2 基于比较函数构造
// 自定义比较函数
struct compare {
bool operator()(int a, int b) {
return a > b; // 最小堆
}
};
priority_queue<int, vector<int>, compare> custom_pq;
4.3 使用已有数据初始化
vector<int> vec = {3, 1, 4, 1, 5};
priority_queue<int> pq(vec.begin(), vec.end()); // 使用迭代器范围构造
5. 容量操作
5.1empty()
if (pq.empty()) {
cout << "优先级队列为空";
}
5.2size()
cout << "优先级队列大小: " << pq.size();
6. 元素访问
6.1top()
if (!pq.empty()) {
cout << "最高优先级元素: " << pq.top();
}
7. 修改操作
7.1push()
pq.push(10); // 插入元素 pq.push(20); pq.push(5);
7.2emplace()
pq.emplace(15); // 原地构造元素(避免拷贝)
7.3pop()
if (!pq.empty()) {
pq.pop(); // 移除最高优先级元素
}
7.4swap()(c++11)
priority_queue<int> pq2; pq.swap(pq2); // 交换两个优先级队列
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;
// 自定义比较函数示例
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. 底层容器与比较函数
9.1 底层容器选择
priority_queue可以基于以下容器实现：
vector（默认）：随机访问性能好，适合堆操作deque：两端操作高效，但内存使用不如vector紧凑
9.2 比较函数
less<t>（默认）：最大堆，大元素优先greater<t>：最小堆，小元素优先- 自定义比较函数：实现复杂排序逻辑
// 自定义比较函数示例：按字符串长度排序
struct lengthcompare {
bool operator()(const string& a, const string& b) {
return a.length() < b.length(); // 长度大的优先
}
};
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(log2n)o(\log_2 n)o(log2n)pop(): o(log2n)o(\log_2 n)o(log2n)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：内存局部性好，通常性能更优deque：在某些情况下可能提供更好的性能
12. 注意事项
- 调用
top()或pop()前必须检查队列是否为空 priority_queue不提供迭代器，无法遍历内部元素- 自定义比较函数需要严格弱序
- 默认是最大堆，要创建最小堆需要显式指定
greater<t>
13. priority_queue与其他容器比较
| 特性 | priority_queue | queue | set |
|---|---|---|---|
| 排序方式 | 按优先级 | fifo | 按键值排序 |
| 访问方式 | 仅顶部元素 | 队首和队尾 | 任意元素 |
| 插入复杂度 | o(log2n)o(\log_2 n)o(log2n) | o(1)o(1)o(1) | o(log2n)o(\log_2 n)o(log2n) |
| 删除复杂度 | o(log2n)o(\log_2 n)o(log2n) | o(1)o(1)o(1) | o(log2n)o(\log_2 n)o(log2n) |
| 重复元素 | 允许 | 允许 | 不允许 |
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论