C++中priority_queue是基于堆的容器适配器，默认为大顶堆，自动排序并优先弹出最大值；通过std::greater可改为小顶堆；底层使用vector存储，借助push_heap和pop_heap维护堆性质；支持自定义类型，需重载operator<或提供比较结构体；也可手动实现简化版堆操作。
在C++中，priority_queue 是一个基于堆（heap）实现的容器适配器，能够自动将元素按照优先级排序，默认是大顶堆（最大值优先）。它并不像普通队列那样遵循先进先出原则，而是每次取出当前优先级最高的元素。
priority_queue 的基本用法
在 C++ 标准库中，priority_queue 定义在 <queue> 头文件中。使用方式如下：
默认大顶堆（最大值优先）：
#include <queue>
#include <iostream>
<p>std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
while (!pq.empty()) {
std::cout << pq.top() << " "; // 输出：30 20 10
pq.pop();
}</p>小顶堆（最小值优先）：
立即学习“C++免费学习笔记（深入）”；
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
这里第三个模板参数指定比较函数对象，使用 std::greater<int> 实现升序，即最小值在 top。
priority_queue 的底层原理
priority_queue 实际上是一个堆结构的封装，通常基于完全二叉树，使用数组（如 vector）存储。其核心操作依赖于两个算法：
- 向上调整（push_heap）：插入新元素后，从底部向上调整以维持堆性质。
- 向下调整（pop_heap）：删除堆顶后，将最后一个元素移到顶部，再向下调整。
这些操作的时间复杂度为 O(log n)，而访问堆顶是 O(1)。
C++ STL 中的 priority_queue 默认使用 std::vector 作为底层容器，并通过 std::make_heap、std::push_heap、std::pop_heap 等函数维护堆结构。
自定义数据类型的优先队列
如果要存储自定义类型（如结构体），需要提供比较逻辑。有两种方式：
方法一：重载 operator<
struct Person {
int age;
std::string name;
// 重载小于号，用于大顶堆（年龄大的优先）
bool operator<(const Person& p) const {
return age < p.age;
}
};
std::priority_queue<Person> pq;
方法二：自定义比较结构体
struct Compare {
bool operator()(const Person& a, const Person& b) {
return a.age < b.age; // 大顶堆
}
};
std::priority_queue<Person, std::vector<Person>, Compare> pq;
手动实现一个简单的优先队列
虽然标准库提供了 priority_queue，但理解其手动实现有助于掌握原理。以下是一个简化版的大顶堆实现：
#include <vector>
#include <iostream>
<p>class MaxPriorityQueue {
private:
std::vector<int> heap;</p><pre class='brush:php;toolbar:false;'>void sift_up(int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (heap[idx] <= heap[parent]) break;
std::swap(heap[idx], heap[parent]);
idx = parent;
}
}
void sift_down(int idx) {
int n = heap.size();
while (idx < n) {
int left = 2 * idx + 1;
int right = 2 * idx + 2;
int max_idx = idx;
if (left < n && heap[left] > heap[max_idx])
max_idx = left;
if (right < n && heap[right] > heap[max_idx])
max_idx = right;
if (max_idx == idx) break;
std::swap(heap[idx], heap[max_idx]);
idx = max_idx;
}
}public: void push(int val) { heap.push_back(val); sift_up(heap.size() - 1); }
void pop() {
if (heap.empty()) return;
std::swap(heap[0], heap.back());
heap.pop_back();
sift_down(0);
}
int top() { return heap.empty() ? -1 : heap[0]; }
bool empty() { return heap.empty(); }};
这个实现包含了基本的插入、删除和访问操作，使用数组模拟完全二叉树结构，通过 sift_up 和 sift_down 维护堆性质。
基本上就这些。C++ 的 priority_queue 封装得很好，大多数情况下直接使用标准库即可。了解其背后是堆结构，以及如何通过比较函数控制排序方向，就能灵活应对各种优先级调度场景。
