C++优先队列怎么用 C++ priority_queue大顶堆小顶堆用法【高阶】

priority_queue默认是大顶堆，top()返回最大元素；其第三个模板参数默认为std::less，基于operator

priority_queue 默认是大顶堆还是小顶堆

默认是大顶堆——也就是 top() 返回最大元素。这是因为它的第三个模板参数默认是 std::less，而 std::less 在底层调用 operator，导致堆按“父节点 > 子节点”维护，即最大堆。

容易踩的坑：误以为“优先级高就排前面”等于“数值小优先”，结果发现 priority_queue 弹出的是最大值，和预期相反。

• 要小顶堆，必须显式传入 std::greater（需 #include ）
• std::greater 要求 T 支持 operator>；自定义类型需重载该运算符，或提供仿函数
• 别写成 priority_queue, greater（c++20 之前不支持类模板参数推导，必须写 greater）

自定义比较器实现小顶堆（含结构体）

对结构体或复杂类型，不能只靠 greater，得自己写比较逻辑。关键是：priority_queue 的比较器定义的是“是否应该排在后面”，即 comp(a, b) == true 表示 a 应该比 b 更“靠后”（即 b 优先级更高）。

所以小顶堆的比较器实际是“a > b”，不是“a

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

struct Node {     int val;     int id; }; // 小顶堆：按 val 升序；val 相同时按 id 升序 auto cmp = [](const Node& a, const Node& b) {      return a.val > b.val || (a.val == b.val && a.id > b.id);  }; priority_queue<node, vector, decltype(cmp)> pq(cmp);

• Lambda 必须捕获为空（否则不能作为模板参数），所以用 decltype(cmp) + 构造函数传入实例
• 如果用 functor 类，需确保 operator() 是 const 且 noexcept（尤其在性能敏感场景）
• 别在比较器里做耗时操作（如字符串比较、IO），它会在每次 push/pop 时频繁调用

priority_queue 没有迭代器，怎么调试或遍历

它不提供迭代器接口，也不能直接访问内部容器。强行遍历时，唯一安全的方式是「拷贝后逐个弹出」，但会清空原队列。

调试建议：

• 临时改用 vector + make_heap/push_heap/pop_heap，它们允许直接访问底层 vector
• 用 ide 的内存视图看其内部 c 成员（比如在 GDB 中 p pq.c），但这依赖实现，不跨平台
• 封装一层带日志的 wrapper：每次 push 记录，top 前断点，避免依赖遍历

注意：priority_queue 的底层容器默认是 vector，但你不能假设 pq.size() 和 vector 下标一一对应——因为堆结构是完全二叉树映射，顺序不是插入顺序。

性能与替代方案：什么时候不该用 priority_queue

单次 push/pop 是 O(log n)，看着不错，但常被忽略的是：它不支持修改已有元素优先级（decrease-key），也不支持按值删除。

• 需要动态调整优先级？考虑 std::set 或手写配对堆 / 斐波那契堆（后者 STL 没提供）
• 需要删除任意元素？用 set + 自定义比较，或标记删除 + 惰性清理（while (!pq.empty() && deleted[pq.top()]) pq.pop();）
• 元素极少（n ）？直接用 vector + min_element 可能更快，避免堆维护开销

真正关键的不是“会不会用”，而是清楚它只适合“只增删顶、不改中”的场景——一旦需求越界，硬套只会让代码越来越难维护。