c++中priority_queue怎么自定义排序_c++优先队列【教程】

priority_queue 默认是大根堆，top() 返回最大元素；底层使用 std::less，即 a b.x。

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

默认是大根堆，也就是 top() 返回最大元素。底层用 std::less 作为比较器，等价于 a —— 注意：这个“小于”决定的是「谁该被优先弹出」的逻辑反向：当 comp(a, b) 为 true，表示 a 应该排在 b **之前**（即更“优先”），但 priority_queue 的堆结构实际按「父节点比子节点大」组织，所以 less 导致最大值在顶。

常见误解：以为 less 就是“小的优先”，其实它控制的是堆的排序谓词，不是直观的“升序/降序”。

• 要小根堆（最小值在 top()）：传 std::greater
• 自定义类型必须提供可调用的比较对象，不能只重载 operator 就完事（除非你用默认模板参数）
• 注意第三个模板参数是类型，不是实例：priority_queue, greater>，不是 greater()

怎么给 struct 自定义 priority_queue 比较规则？

最稳妥的方式是单独写一个仿函数（functor）或用 lambda（C++20 起支持，但需配合 decltype 且不能直接用于模板参数）。推荐 functor：

struct Node {
    int x, y;
    Node(int x, int y) : x(x), y(y) {}
};

struct Compare {
    bool operator()(const Node& a, const Node& b) {
        return a.x > b.x; // 小根堆按 x 排；注意：这里写 > 表示“a 优先级低于 b”时返回 true，即 a 应该沉下去
    }
};

priority_queue, Compare> pq;

• 函数体里写 a.x > b.x 才能得到「x 小的在 top」—— 因为 priority_queue 把返回 true 的 pair 当作「a 不如 b 优先」来调整堆
• 如果用 auto cmp = [](const Node& a, const Node& b) { return a.x > b.x; };，不能直接塞进模板参数，得用 priority_queue, decltype(cmp)> pq(cmp);（C++11 起支持带状态的比较器）
• 别在 operator 里改逻辑来凑合：容易和 set/map 行为冲突，语义混乱

为什么用了 greater 还报错 “no match for operator

典型错误场景：对自定义类型写 priority_queue, greater>，编译失败提示找不到 operator。

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

原因：std::greater 内部仍会调用 operator（它等价于 return b ），所以最终还是依赖 T 支持 。它不是“绕过比较”，而是“换一种方式调用”。

• 正确解法：要么实现 bool operator，要么不使用 greater，改用显式 functor 或 lambda
• 如果类有多个字段想复合排序（比如先按 cost 升序，再按 id 降序），greater 完全无能为力，必须手写比较逻辑
• 注意：即使你只用 priority_queue，也建议把 operator 定义成符合直觉的“严格弱序”（如升序），避免其他容器误用时行为不一致

用 vector 初始化 priority_queue 时排序规则生效吗？

生效，但仅限于构造时一次性建堆。例如：

vector v = {3, 1, 4};
priority_queue, greater> pq(v.begin(), v.end());
// pq.top() == 1 ✅

• 底层调用的是 make_heap，时间复杂度 O(n)，不是逐个 push 的 O(n log n)
• 但 vector 必须是可随机访问的容器；如果是 list 或其他，无法直接初始化
• 初始化后所有后续操作（push/pop）都继续遵守该比较规则，不会回退到默认
• 如果 vector 本身已按某种顺序排好，别指望它“保持原序”——堆结构必然重排