1.priority_queue概述

priority_queue是C++标准模板库(STL)中的容器适配器，提供优先级队列功能。它保证优先级最高的元素总是位于队列前端，默认情况下是最大堆实现（最大元素优先）。

2. 基本特性

  • 优先级排序：元素按优先级排序，默认最大元素在前
  • 容器适配器：基于其他序列容器实现（默认vector）
  • 限制访问：只允许访问顶部元素
  • 高效操作：插入和删除操作时间复杂度为O(log⁡2n)O(\log_2 n)O(log2​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. 构造函数与初始化

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(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：内存局部性好，通常性能更优
  • deque：在某些情况下可能提供更好的性能

12. 注意事项

  1. 调用top()或pop()前必须检查队列是否为空
  2. priority_queue不提供迭代器，无法遍历内部元素
  3. 自定义比较函数需要严格弱序
  4. 默认是最大堆，要创建最小堆需要显式指定greater<T>

13. priority_queue与其他容器比较

特性 priority_queue queue set
排序方式 按优先级 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)
重复元素 允许 允许 不允许

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持本站。

声明：本站（华域联盟www.cnhackhy.com）所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。