c++中priority_queue怎么用_c++优先队列使用指南【教程】

priority_queue 默认是最大堆，因第三模板参数默认为 std::less，其调用 a

直接说结论：priority_queue 默认是最大堆，不是最小堆；想用最小堆必须显式指定比较器，否则 top() 返回的是最大值，不是你想要的“优先级最高”的最小耗时/最小距离等。

为什么 priority_queue 默认是最大堆？

因为它的第三个模板参数默认是 std::less，而 std::less 在 a 为真时返回 true —— 这会让大数“优先级更高”，所以堆顶始终是最大元素。

常见误用场景：写 Dijkstra 或 BFS 求最短路时，把 pair（距离, 节点）塞进去，结果每次 top() 取出的是距离最大的节点，算法直接跑飞。

• 要最小堆（小距离优先）：用 priority_queue, vector>, greater>>
• 更稳妥写法（避免依赖 greater 对 pair 的特化）：priority_queue, vector>, greater（C++14 起支持透明比较器）
• 自定义结构体？必须重载 operator，且注意语义：如果希望 a “优先级高于” b 时先弹出 a，那就要让 a 返回 false（即按“优先级升序”排，但底层仍按 less 解释）—— 更建议直接传 lambda 或 functor

怎么用 lambda 自定义比较器？

priority_queue 的比较器必须满足严格弱序，且不能是普通 lambda（有闭包，无法作为模板参数），但可以用 decltype + auto 配合 vector 构造：

立即学习“C++免费学习笔记（深入）”；

知识画家

AI交互知识生成引擎，一句话生成知识视频、动画和应用

下载

auto cmp = [](const pair& a, const pair& b) {
    return a.first > b.first; // 小 first 先出队 → 最小堆
};
priority_queue, vector>, decltype(cmp)> pq(cmp);

注意：必须把 cmp 实例传给构造函数，否则运行时报错（空比较器未初始化）。

• lambda 里写 a.first > b.first → 小值优先
• 写 a.first → 大值优先（等效默认 less）
• 不要试图用 [&] 捕获外部变量，会导致类型不可比较或编译失败

push、top、pop 的性能和线程安全

所有操作平均时间复杂度都是 O(log n)，top() 是 O(1)；内部用 vector 实现，不支持迭代器遍历，也不能像 set 那样查某元素是否存在。

• 没有 find 或 contains 成员函数 —— 想查元素得自己维护一个额外哈希表
• 不是线程安全的：多线程读写必须加锁，哪怕只读 top() 和 empty() 也要注意竞态（empty() 后可能立刻被 pop）
• pop() 不返回值，必须先 top() 再 pop()，别指望它像 Python 的 heappop

最容易忽略的一点：修改已入队元素的值不会触发堆调整。比如存了 struct Node { int cost; int id; };，push 后改了某个 Node.cost，堆结构完全不变 —— 此时要么重新 push 新对象，要么换用 std::set。