c++中如何使用std::priority_queue实现小顶堆_c++优先队列配置【实例】

std::priority_queue默认是大顶堆；要实现小顶堆必须显式传入std::greater作为第三个模板参数，或自定义比较器使operatorb.cost。

std::priority_queue 默认是大顶堆，不是小顶堆

直接声明 std::priority_queue 得到的是最大堆（顶部是最大值），这和多数人直觉里“优先队列=取最小”相悖。要得到小顶堆，必须显式指定比较器 —— 不能靠“反向插入”或“取负数”这种取巧方式，否则会破坏语义且易出错。

正确配置小顶堆的三种等效写法

核心是传入 std::greater 作为第三个模板参数，它要求容器支持随机访问（std::vector 默认满足）：

• 最常用：

  std::priority_queue, std::greater> min_heap;

• 用 using 别名简化：

  using MinHeap = std::priority_queue, std::greater>;
  MinHeap min_heap;

• Lambda 不行 —— 比较器类型必须在编译期确定，不能用运行时对象

常见错误：把 std::less 当成小顶堆

std::less 是默认比较器，等价于 operator，但它在 priority_queue 中控制的是“谁该被优先弹出”的逻辑：标准库按“堆序性质”定义，即父节点 *不小于* 子节点才构成大顶堆；所以 std::less 实际维持的是大顶堆（因为 a 成立时，b 更“优先”留在顶部）。

• 误写：std::priority_queue, less> → 还是大顶堆
• 混淆根源：把比较器语义和堆序方向搞反了；记住口诀：“比较器返回 true 表示左操作数‘优先级更低’”
• 验证方法：插入 {3,1,4} 后调用 top()，小顶堆应返回 1，否则配置错了

自定义类型的小顶堆必须重载 operator

比如有个结构体 node，想按 cost 字段建小顶堆：

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

struct Node {
    int id;
    int cost;
};

// 方式一：重载 operator<
bool operator<(const Node& a, const Node& b) {
    return a.cost > b.cost; // 注意：这里要反着写！
}
std::priority_queue, less> pq;

// 方式二：独立仿函数（更清晰）
struct CompareCost {
    bool operator()(const Node& a, const Node& b) {
        return a.cost > b.cost;
    }std::priority_queue, CompareCost> pq;

关键点：无论哪种方式，比较逻辑都必须让“代价小的元素优先级更高”，所以条件中要用 >（即当 a.cost > b.cost 时，b 应该浮到顶部）。这个反直觉的翻转最容易漏掉。

小顶堆配置本身不难，但比较器方向、自定义类型的翻转逻辑、以及和容器底层堆序的耦合关系，三者叠加后出错率很高 —— 尤其在调试 Dijkstra 或 BFS 变种时，一个 > 写成 就会让算法退化成 O(n²)。