优先队列概述
priority_queue 是 C++ 标准模板库（STL）中一个非常实用的容器适配器，它基于堆（Heap）数据结构实现。默认情况下，它是一个最大堆，即每次取出的都是当前集合中优先级最高的元素。
在实际开发中，无论是算法竞赛中的贪心策略，还是操作系统调度、实时交易系统的任务处理，只要涉及'按优先级排序'的需求，优先队列都是首选方案。
底层结构与特性
优先队列的底层容器默认是 vector。选择连续内存结构不仅适合堆的随机访问需求，还能带来更好的缓存命中率。虽然头文件包含在 <queue> 中，但它的行为更接近于一种特殊的队列——只允许在队尾插入，在队首（堆顶）访问和删除。
核心特点：
- 存储方式：数组形式存储的完全二叉树。
- 默认行为：大顶堆（最大值在顶部）。
- 自定义小顶堆：需传入比较器
greater<int>。 - 操作限制：只能访问堆顶元素，无法遍历中间节点。
- 时间复杂度：访问 O(1)，插入/删除 O(log n)。
API 使用指南
初始化
支持默认构造或范围初始化：
// 默认初始化
priority_queue<int> pq;
// 范围初始化（例如从数组）
int arr[] = {1, 5, 3};
priority_queue<int> pq2(arr, arr + 3);
基本操作
- 插入元素：
push(val)，自动调整堆结构，O(log n)。 - 访问堆顶：
top()，返回最高优先级元素，不删除，O(1)。 - 删除堆顶：
pop()，移除当前最大值，并重新调整堆，O(log n)。 - 判断空：
empty()，若为空返回 true。 - 获取大小：
size()，返回当前元素个数。
V.push(val); // 插入
V.top(); // 查看
V.pop(); // 弹出
V.size(); // 大小
V.empty(); // 判空
深入底层：模拟实现
理解优先队列的最佳方式是亲手实现它。既然底层是 vector，我们只需要封装一层逻辑，维护堆的性质即可。
类模板定义
template<class T, class container = std::vector<T>>
class priority_queue {
public:
// 构造函数通常可省略，依赖 vector 默认构造
private:
container x; // 底层容器
};
插入逻辑：向上调整
插入时，先将元素追加到尾部，然后从该位置开始向上调整，直到满足父节点大于子节点的大顶堆性质。
void push(const T& value) {
x.push_back(value);
shiftUp(x.size() - 1); // 向上调整
}
void shiftUp(int child) {
while (child > 0) {
int parent = (child - 1) / 2;
if (x[child] > x[parent]) {
std::swap(x[child], x[parent]);
child = parent;
} else {
break; // 已满足堆性质
}
}
}
删除逻辑：向下调整
删除堆顶元素不能直接删，否则会导致空缺。标准做法是将堆顶与最后一个元素交换，删除尾部，然后从根节点开始向下调整。
void pop() {
if (!x.empty()) {
std::swap(x[0], x.back());
x.pop_back();
shiftDown(0); // 向下调整
}
}
void shiftDown(int parent) {
int child = 2 * parent + 1; // 左孩子
while (child < x.size()) {
// 如果右孩子存在且比左孩子大，选右孩子
if (child + 1 < x.size() && x[child + 1] > x[child]) {
child++;
}
// 如果父节点小于较大的子节点，则交换
if (x[parent] < x[child]) {
std::swap(x[parent], x[child]);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
完整测试示例
void test_priority_queue() {
std::priority_queue<int> pq;
// 插入一组数据
for (int val : {10, 15, 5, 20, 0, 25}) {
pq.push(val);
}
// 输出堆顶（最大值）
std::cout << "Top: " << pq.top() << std::endl;
// 弹出堆顶
pq.pop();
std::cout << "New Top: " << pq.top() << std::endl;
// 检查是否为空
std::cout << "Empty: " << pq.empty() << std::endl;
}
