盘锦网站建设公司快速网站搭建
文章目录
- 一、容器概览与核心特性
- 核心特性速览
- 二、底层实现原理
- 1. 二叉堆结构
- 2. 容器适配器架构
- 三、核心操作详解
- 1. 容器初始化
- 2. 元素操作接口
- 3. 自定义优先队列
- 四、实战应用场景
- 1. 任务调度系统
- 2. 合并K个有序链表
- 五、性能优化策略
- 1. 底层容器选择
- 2. 批量建堆优化
- 六、注意事项与陷阱
- 1. 常见错误操作
- 2. 比较函数要求
- 七、C++新标准增强
- 1. C++11移动语义
- 2. C++17节点操作（需要底层容器支持）
- 总结与最佳实践
- 选择优先队列的三大条件
- 性能优化清单
- 典型应用场景
一、容器概览与核心特性
std::priority_queue是C++标准模板库（STL）提供的容器适配器，实现优先队列数据结构。元素按优先级排序，队首始终为最大（默认）或最小元素。底层通常基于vector实现堆结构。
核心特性速览
| 特性 | 说明 |
|---|---|
| 底层容器 | 默认vector，可指定deque |
| 时间复杂度 | 插入O(log n)，取顶O(1) |
| 空间复杂度 | O(n) |
| 迭代器支持 | ❌ 不支持遍历操作 |
| 头文件 | <queue> |
| 排序方向 | 默认大顶堆（可通过比较器修改） |
二、底层实现原理
1. 二叉堆结构
priority_queue通过完全二叉树实现，满足堆性质：
-
父节点值 ≥ 子节点值（大顶堆）
-
数组存储实现：对于索引i的节点：
-
父节点：
(i-1)/2 -
左子节点：
2*i + 1 -
右子节点：
2*i + 2
-
// 堆操作关键函数示意void heapify_up(int i) {while (i > 0 && heap[(i-1)/2] < heap[i]) {swap(heap[(i-1)/2], heap[i]);i = (i-1)/2;}}void heapify_down(int i) {int max = i;if (left(i) < size && heap[left(i)] > heap[max]) max = left(i);if (right(i) < size && heap[right(i)] > heap[max])max = right(i);if (max != i) {swap(heap[i], heap[max]);heapify_down(max);}}
2. 容器适配器架构
类声明原型：
template<typename T,typename Container = vector<T>,typename Compare = less<typename Container::value_type>> class priority_queue;
支持容器需满足：
front()push_back()pop_back()- 随机访问迭代器
三、核心操作详解
1. 容器初始化
// 默认大顶堆priority_queue<int> maxHeap;// 小顶堆初始化priority_queue<int, vector<int>, greater<int>> minHeap;// 自定义比较器struct Task {int priority;string description;};auto cmp = [](const Task& a, const Task& b) {return a.priority < b.priority; // 大顶堆};priority_queue<Task, vector<Task>, decltype