C++ priority_queue怎么用 C++优先队列与自定义排序【堆】

std::priority_queue 默认是大根堆，顶部元素最大；其底层使用 std::less 比较器，使较小元素“优先级更高”；自定义类型需重载 operator

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

默认是大根堆，也就是顶部元素最大。这容易让人误解为“优先级高就先出”，但其实 std::priority_queue 的底层是 std::less 比较器，对类型 T 调用 a ，所以更大的元素被“优先”弹出。

常见错误：想实现最小堆却直接写 priority_queue，结果每次 top() 拿到的是最大值，和预期相反。

• 要小根堆，必须显式指定比较器：priority_queue, greater>
• greater 对应 a > b 判断逻辑，让更小的数“优先级更高”
• 注意模板参数顺序固定：``，不能只改最后一个

自定义结构体怎么进 priority_queue

必须提供可调用的比较逻辑，否则编译失败，报错类似：invalid operands to binary expression ('const node' and 'const Node')。

最稳妥的方式是重载 operator，但要注意语义一致性——如果你希望小的 Node 先出队，就让 a 在 a 应该排在 b 前面时返回 true（即模拟“小于”关系）。

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

struct Node {     int val, id;     bool operator<(const Node& rhs) const {         return val > rhs.val; // 注意这里是 >     } }; priority_queue pq; // 小根堆按 val

• 别写成 val ，那会变成大根堆
• 如果不想改结构体，可用 lambda + decltype，但 c++11 不支持 lambda 作模板参数，得用函数对象（struct + operator()）
• 成员变量若为 private，operator 需声明为 friend 或提供 public getter

为什么传 greater 要加尖括号而 less 不用

因为 std::priority_queue 模板声明中第三个参数默认是 std::less，它是个类模板，实例化时需要类型信息；而 greater 是具体类型，必须带模板实参。

等价写法：priority_queue, less> 和 priority_queue 效果一样，只是显式写出默认行为。

• 漏掉 会编译失败：greater 不是类型，greater 才是
• 容器类型第二个参数不能省略：比如想用 deque，必须写全 priority_queue, greater>
• 所有比较器必须满足 Strict Weak Ordering，禁止用 =、>= 等非严格序操作

priority_queue 和手写堆比有什么限制

它不支持修改中间元素、不支持随机访问、无法获取某个元素当前索引，也没有 decrease_key 或 increase_key 接口。本质上是个“只能 push / top / pop”的黑盒堆。

典型陷阱：想更新已入队元素的优先级，结果只能重新 push 一个新节点，靠后续 top() 时检查是否过期（lazy deletion），额外维护一个标记数组或哈希表。

• 无法遍历内部数据，size() 可查，但没有 begin()/end()
• 内存布局不保证连续（虽然底层 vector 是连续的，但接口不暴露）
• 多线程下不安全，push/pop 都需外部加锁

真要动态调整优先级，考虑 std::set 或第三方库如 boost::heap，而不是硬套 priority_queue。