17370845950

priority_queue默认是大根堆，要小根堆需显式指定容器和比较器：priority_queue pq；自定义排序须用仿函数类，operator()返回true表示a优先级低于b。

priority_queue 默认是大根堆（最大堆），想用小根堆或自定义排序，不能直接传 lambda，得靠仿函数或 std::greater。

怎么让 priority_queue 变成小根堆

默认构造的 priority_queue 顶部是最大值；要最小值在顶，必须显式指定容器和比较器：

• 用 std::greater：需要包含 ，且第三个模板参数填它
• 底层容器默认是 std::vector，第二个参数必须写出来（即使不改）

正确写法：

priority_queue, greater> pq;

自定义结构体排序：必须写仿函数类

lambda 不能作为模板非类型参数，所以不能直接传。得定义一个可调用类型：

• 重载 operator() 的 struct/class（推荐，清晰、可复用）
• 注意返回值

  

  语义：返回 true 表示第一个参数“优先级更低”，即排在后面（priority_queue 是“less 为大根，greater 为小根”，本质是“判断 a 是否该排在 b 后面”）
• 比如按 Node.val 升序排（小根），仿函数里写 a.val > b.val

示例：

struct Node { int val; };
struct Compare {
    bool operator()(const Node& a, const Node& b) {
        return a.val > b.val; // 小根堆：val 小的在顶
    }
};
priority_queue, Compare> pq;

用 function 对象或函数指针？不推荐

理论上可以传函数指针或 std::function，但会导致运行时开销（虚调用/堆分配），且模板实例化更复杂：

• priority_queue, function> 要求每次构造时传比较函数，无法作为类成员静态声明
• 编译器难优化，性能不如仿函数类
• 绝大多数场景没必要，仿函数完全够用

真要动态改逻辑，建议封装一层，内部仍用固定仿函数 + 外部状态变量控制行为。

常见编译错误和坑

这些错几乎都源于模板参数顺序或语义理解偏差：

• error: type/value mismatch at argument 3：第三个参数不是类型（比如写了 greater() 带括号，应去掉）
• 堆顶结果和预期相反：检查仿函数里 operator() 返回逻辑，记清楚“返回 true = a 优先级低于 b”
• 结构体没写 const 引用参数：导致大量拷贝，尤其对象大时明显变慢
• 忘记指定底层容器（第二个参数）：priority_queue 是非法的，必须写全三个

最易忽略的是：仿函数里的比较逻辑和直觉相反——它不是“是否应该交换”，而是“是否应该把 a 放在 b 下面”。这个反直觉点，调试时花的时间往往比写代码还多。