115 std::priority_queue
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 基本概念
std::priority_queue 是 C++ 标准模板库(STL)中的一个容器适配器，它提供了一种优先级队列的实现。
1.1 定义
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
template<
2
class T,
3
class Container = std::vector<T>,
4
class Compare = std::less<typename Container::value_type>
5
> class priority_queue;
1.2 特点
- 不是严格的 FIFO 结构，而是按照优先级出队
- 默认情况下，最大元素总是位于队列顶部（最大堆）
- 底层通常使用堆数据结构实现
2. 核心操作
2.1 构造函数
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
// 默认构造函数
2
priority_queue<int> pq1;
3
4
// 使用指定比较函数的构造函数
5
priority_queue<int, vector<int>, greater<int>> pq2;
6
7
// 从已有容器构造
8
vector<int> vec = {3, 1, 4, 1, 5};
9
priority_queue<int> pq3(vec.begin(), vec.end());
10
11
// 使用自定义比较函数
12
auto cmp = [](int a, int b) { return a > b; };
13
priority_queue<int, vector<int>, decltype(cmp)> pq4(cmp);
2.2 主要成员函数
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
push(const T& value) | 插入元素 | O(log n) |
emplace(Args&&... args) | 原位构造元素 | O(log n) |
pop() | 移除顶部元素 | O(log n) |
top() | 访问顶部元素 | O(1) |
size() | 返回元素数量 | O(1) |
empty() | 检查是否为空 | O(1) |
2.3 示例代码
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <queue>
2
#include <vector>
3
#include <iostream>
4
5
int main() {
6
std::priority_queue<int> pq;
7
8
pq.push(30);
9
pq.push(10);
10
pq.push(20);
11
pq.push(5);
12
13
std::cout << "Top element: " << pq.top() << std::endl; // 30
14
15
pq.pop();
16
std::cout << "After pop, top element: " << pq.top() << std::endl; // 20
17
18
return 0;
19
}
3. 底层容器与比较函数
3.1 底层容器
- 默认使用
std::vector - 也可以使用
std::deque - 必须满足序列容器的要求，并提供以下函数：
front()push_back()pop_back()
3.2 比较函数
- 默认使用
std::less<T>，形成最大堆 - 可以使用
std::greater<T>形成最小堆 - 可以自定义比较函数
自定义比较函数示例
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
struct Person {
2
std::string name;
3
int age;
4
};
5
6
auto cmp = [](const Person& a, const Person& b) {
7
return a.age < b.age; // 年龄大的优先级高
8
};
9
10
std::priority_queue<Person, std::vector<Person>, decltype(cmp)> pq(cmp);
4. 应用场景
4.1 典型应用
- 任务调度系统
- Dijkstra 最短路径算法
- 哈夫曼编码
- 合并 K 个有序链表
- 数据流的中位数问题
4.2 示例：合并 K 个有序链表
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
struct ListNode {
2
int val;
3
ListNode *next;
4
ListNode(int x) : val(x), next(nullptr) {}
5
};
6
7
struct CompareNode {
8
bool operator()(const ListNode* a, const ListNode* b) {
9
return a->val > b->val;
10
}
11
};
12
13
ListNode* mergeKLists(vector<ListNode*>& lists) {
14
priority_queue<ListNode*, vector<ListNode*>, CompareNode> pq;
15
16
for (auto list : lists) {
17
if (list) pq.push(list);
18
}
19
20
ListNode dummy(0);
21
ListNode* tail = &dummy;
22
23
while (!pq.empty()) {
24
ListNode* node = pq.top();
25
pq.pop();
26
27
tail->next = node;
28
tail = tail->next;
29
30
if (node->next) {
31
pq.push(node->next);
32
}
33
}
34
35
return dummy.next;
36
}
5. 注意事项
5.1 性能考虑
- 插入和删除操作的时间复杂度为 O(log n)
- 访问顶部元素的时间复杂度为 O(1)
- 不提供迭代器，不能遍历所有元素
5.2 常见错误
❶ 在空队列上调用 top() 或 pop()
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::priority_queue<int> pq;
2
// 错误: pq.top(); // 未定义行为
3
if (!pq.empty()) {
4
pq.top();
5
}
❷ 错误地使用比较函数导致优先级顺序不符合预期
❸ 误认为 priority_queue 是有序容器（它只是保证顶部元素是最大/最小的）
6. 与其他容器的比较
| 特性 | priority_queue | set/multiset | map/multimap |
|---|---|---|---|
| 排序 | 部分排序（堆） | 完全排序 | 完全排序 |
| 查找顶部 | O(1) | O(1) (begin()) | O(1) (begin()) |
| 插入 | O(log n) | O(log n) | O(log n) |
| 删除顶部 | O(log n) | O(1) (begin()) | O(1) (begin()) |
| 随机访问 | 不支持 | 不支持 | 不支持 |
| 重复元素 | 允许 | multiset允许 | multimap允许 |
7. 扩展知识
7.1 底层堆操作
priority_queue 底层使用以下堆算法：
- std::make_heap
- std::push_heap
- std::pop_heap
7.2 线程安全
priority_queue不是线程安全的- 多线程环境下需要外部同步
7.3 替代方案
- 对于需要频繁更新优先级的场景，可以考虑使用
std::set - 对于需要更复杂操作的场景，可以考虑使用 Boost.Heap 库
8. 练习题目
- 实现一个支持动态更新的优先级队列
- 使用
priority_queue解决 Top K 问题 - 实现一个支持重复元素的优先级队列
- 使用
priority_queue模拟进程调度系统
9. 总结
std::priority_queue 是 C++ 中一个非常有用的容器适配器，特别适合需要按优先级处理元素的场景。理解其底层实现原理、比较函数的使用方法以及适用场景，能够帮助我们在解决实际问题时做出更合适的选择。
std::priority_queue 的常用 API 整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
| 构造函数 | 创建优先队列 | priority_queue(const Compare& = Compare(), const Container& = Container()); | std::priority_queue<int> pq; | 默认构造最大堆（使用 std::less 比较器）。 |
| push | 插入元素 | void push(const T& value); | pq.push(10); | 插入元素并自动维护堆结构。 |
| emplace | 原地构造元素 | template<class... Args> void emplace(Args&&... args); | pq.emplace(10); | 避免拷贝，直接构造元素。 |
| pop | 移除堆顶元素 | void pop(); | pq.pop(); | 移除堆顶（优先级最高元素），需保证队列非空。 |
| top | 访问堆顶元素 | const T& top() const; | int val = pq.top(); | 返回堆顶元素（不可修改），需保证队列非空。 |
| size | 返回元素数量 | size_type size() const; | size_t s = pq.size(); | 返回当前队列中的元素个数。 |
| empty | 检查是否为空 | bool empty() const; | if (pq.empty()) { /* ... */ } | 返回 true 如果队列为空。 |
| swap | 交换两个优先队列 | void swap(priority_queue& other); | std::priority_queue<int> pq2; pq.swap(pq2); | 交换两个队列的内容（包括底层容器和比较器）。 |
完整代码示例
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <queue>
3
#include <vector>
4
5
int main() {
6
// 1. 构造函数（默认最大堆）
7
std::priority_queue<int> maxHeap;
8
9
// 2. push 插入元素
10
maxHeap.push(30);
11
maxHeap.push(10);
12
maxHeap.push(20);
13
14
// 3. top 访问堆顶（最大值）
15
std::cout << "Top: " << maxHeap.top() << std::endl; // 输出 30
16
17
// 4. pop 移除堆顶
18
maxHeap.pop();
19
std::cout << "After pop, Top: " << maxHeap.top() << std::endl; // 输出 20
20
21
// 5. 最小堆示例（需指定比较器和底层容器）
22
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
23
minHeap.push(5);
24
minHeap.push(1);
25
minHeap.push(3);
26
std::cout << "MinHeap Top: " << minHeap.top() << std::endl; // 输出 1
27
28
return 0;
29
}
关键注释
- 比较器：默认
std::less<T>生成最大堆，std::greater<T>生成最小堆。 - 底层容器：默认为
std::vector<T>，也可用std::deque<T>。 - 复杂度：
push/pop: O(log n)top: O(1)
文章目录