C++ priority_queue大顶堆小顶堆 _ 优先队列自定义优先级【实战】

很多人用C++的std::priority_queue时，总觉得默认是大顶堆，想用小顶堆或者自定义优先级就得改改push或者top的逻辑——其实这里有个关键点容易踩坑：必须显式传入比较器，不能只改表面操作。

默认是大顶堆，想用小顶堆或自定义优先级，必须显式传入比较器，不能只改push或top逻辑。

为什么 priority_queue 默认是大顶堆？

其实，C++标准库的std::priority_queue底层用的是最大堆（max-heap），所以top()返回的是最大元素。它的第三个模板参数默认是std::less，而std::less在调用operator<时，会让“更大的值”被优先弹出——这正是大顶堆的行为逻辑。

很多人会误解，以为把vector换成deque，或者改改compare函数体就能翻转顺序——其实不然。关键就在于比较器的语义是否与堆维护逻辑一致。简单来说：

• std::less相当于a < b，堆中“b比a大”时b更靠前，所以是大顶堆。
• std::greater相当于a > b，堆中“b比a小”时b更靠前，所以是小顶堆。
• 自定义仿函数或lambda必须满足严格弱序（strict weak ordering），且返回true表示“左操作数应排在右操作数之后”，即右操作数优先级更高。

小顶堆怎么写？别漏掉第三个模板参数

直接使用std::greater是最稳妥的方案。注意，它是类型名，要写在模板参数里，而不是函数对象实例。如果只写priority_queue, greater>而不加std::前缀，会编译失败（除非有using声明）。

priority_queue, greater> min_heap; // ✅ 小顶堆
min_heap.push(3);
min_heap.push(1);
min_heap.push(4);
// top() == 1

这里有几个容易踩的坑：

• 不能只写priority_queue, greater<>>（C++20才支持类模板参数推导，且需开启C++20）。
• 不能把greater()（带括号的实例）塞进模板参数——那是构造函数调用，不是类型。
• 容器类型（第二个参数）不能省略，即使你只想换比较器。

自定义结构体的优先级：仿函数比lambda更实用

lambda无法作为模板参数，因为它的类型不可名状，所以不能直接用于priority_queue模板声明。必须用仿函数（functor）或函数指针（不推荐）。

struct Task {
    int id;
    int priority;
    bool operator<(const Task& rhs) const { return priority < rhs.priority; }
};

// ❌ 错误：仍按 operator< 构建大顶堆（高 priority 先出）
priority_queue q1;

// ✅ 正确：用仿函数反转逻辑（低 priority 先出）
struct CompareLowPriority {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority > b.priority; // 注意：这里 return true 表示 a 应排在 b 后面 → b 优先级更高
    }
};
priority_queue, CompareLowPriority> q2;

这里有几个需要留意的点：

• 仿函数的operator()返回true，表示第一个参数“优先级更低”，会被堆沉到下面。
• 不要依赖operator<重载来控制优先队列行为——它只影响默认比较器，一旦指定第三个参数，就完全忽略它。
• 如果字段多，比如先比priority，相等再比id，建议在仿函数里手动写清楚逻辑，避免tie引发的临时对象开销。

性能和兼容性陷阱：容器选择与移动语义

priority_queue的第二个模板参数默认是vector，但有些人想换成deque来避免realloc。建议别这么做——deque的随机访问常数因子更大，make_heap、push_heap等算法对deque支持较差，GCC libstdc++甚至可能静默降级为低效路径。

几个实用建议：

• 保持默认的vector，除非你明确测出内存碎片是瓶颈，并且愿意自己封装heap操作。
• 存储大型对象时，确保类型支持移动语义（或至少有noexcept移动构造），否则每次push可能触发深拷贝。
• 用emplace替代push构造对象，避免临时对象；但注意，如果比较器捕获了外部状态（比如闭包），就不能用lambda，只能回退到仿函数加成员变量。

最容易被忽略的一点：比较器对象在队列整个生命周期内必须有效。如果使用绑定局部变量的std::function包装仿函数，很容易出现悬垂问题——优先队列内部不管理比较器生命周期，只保存其副本。