11、priority_queue优先队列：构造、push与pop、仿函数与优先级设置、底层实现（堆）
优先队列，说白了就是一个会自动排序的队列。
普通队列是先进先出，优先队列呢？谁优先级高谁先出。我当年第一次用这个容器时，心里想的是：「这不就是个自动排队的VIP通道吗？」后来在项目中用多了，发现它确实就是这么个东西——只不过底层用的是堆，效率很高。
11.1 优先队列的构造
priority_queue 定义在
#include <queue>
#include <vector>
// 默认构造：大顶堆（最大元素优先）
std::priority_queue<int> pq;
// 指定底层容器为 vector
std::priority_queue<int, std::vector<int>> pq2;
// 指定仿函数为 greater，变成小顶堆
std::priority_queue<int, std::vector<int>, std::greater<int>> pq3;默认情况下，priority_queue 使用 std::vector 作为底层容器，使用 std::less<T> 作为比较仿函数。这意味着：最大的元素总是在队首。
11.2 push 与 pop：入队与出队
priority_queue 的接口非常简洁，就三个核心操作：push、pop、top。
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.push(5);
std::cout << "队首元素: " << pq.top() << std::endl; // 输出 30
pq.pop(); // 移除 30
std::cout << "队首元素: " << pq.top() << std::endl; // 输出 20注意：pop 不会返回被移除的元素。你要先 top() 看一眼，再 pop() 把它扔掉。这个设计我一开始也觉得别扭，但后来想想——如果 pop 直接返回元素，那拷贝开销就大了，尤其是元素类型是复杂对象时。
11.3 仿函数与优先级设置
priority_queue 的第三个模板参数就是用来控制优先级的。默认是 std::less<T>，也就是大顶堆。如果你想改成小顶堆，用 std::greater<T> 就行。
// 小顶堆：最小的元素在队首
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(10);
min_pq.push(30);
min_pq.push(20);
std::cout << min_pq.top() << std::endl; // 输出 10那如果是自定义类型呢？比如一个任务结构体，按优先级排序？
struct Task {
int id;
int priority;
};
// 自定义仿函数
struct CompareTask {
bool operator()(const Task& a, const Task& b) const {
return a.priority < b.priority; // 优先级高的在前
}
};
std::priority_queue<Task, std::vector<Task>, CompareTask> task_queue;这里有个容易搞混的地方：仿函数的返回 true 表示 a 应该排在 b 后面。也就是说，a.priority < b.priority 为 true 时，a 的优先级更低，会被放到后面。这跟 sort 的比较器逻辑是反的，你想想看——堆的调整方向跟排序不一样。
11.4 底层实现：堆
priority_queue 的底层就是二叉堆，具体来说是 std::make_heap、std::push_heap、std::pop_heap 这一套算法。
说白了，priority_queue 就是对堆算法的一个封装。你完全可以用 vector + 堆算法手动实现同样的效果，但 priority_queue 帮你把接口简化了。
// 手动实现堆的效果
std::vector<int> vec = {10, 30, 20, 5};
std::make_heap(vec.begin(), vec.end()); // 建堆
vec.push_back(25);
std::push_heap(vec.begin(), vec.end()); // 插入后调整
std::pop_heap(vec.begin(), vec.end()); // 把最大值移到末尾
vec.pop_back(); // 移除最大值堆的时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| push | O(log n) |
| pop | O(log n) |
| top | O(1) |
| 构造（从已有数据） | O(n) |
为什么 top 是 O(1)？因为堆顶元素就是数组的第一个元素，直接返回就行。push 和 pop 需要调整堆结构，所以是 O(log n)。
11.5 知识体系总览
下面这张图帮你理清 priority_queue 的核心脉络：
11.6 避坑与实战建议
最后，分享几个我在项目中积累的经验：
- 不要用 priority_queue 做遍历——它不支持迭代器，你没法从头到尾看一遍所有元素。如果非要看，只能不断 pop，但那样队列就空了。
- 自定义类型的比较器一定要写对。我曾经把一个优先级队列的仿函数写反了，结果紧急任务一直被压在队尾，线上出了事故。排查了半天才发现是
<和>搞反了。 - 如果元素数量固定，可以考虑用
std::make_heap直接操作 vector，灵活性更高。priority_queue 封装得太死，有些场景反而不方便。 - 多线程环境下注意加锁。priority_queue 本身不是线程安全的，多个线程同时 push/pop 会出问题。我一般会用 mutex 包一层，或者直接用 TBB 的 concurrent_priority_queue。
嗯，关于 priority_queue 就讲这么多。记住它的核心：堆 + 仿函数 = 自动优先级排序。用好了，很多排序相关的需求都能轻松搞定。