c++中如何实现简单的优先队列排序_c++ std::greater比较器应用【详解】

std::priority_queue 默认是大顶堆，不是你想要的小顶堆

很多人一上来就写 std::priority_queue，发现 top() 返回的是最大值，pop 顺序也是从大到小——这其实是默认行为，底层用的是 std::less。如果你需要“最小值优先”（比如 Dijkstra 算法、合并 K 个有序链表），就得显式切换比较器。

用 std::greater 构造小顶堆的正确写法

关键不是只写 std::greater，而是要补全模板参数：第三个参数必须和容器类型（第二个参数）匹配。漏掉任意一个，编译直接报错。

• std::priority_queue, std::greater> ✅ 正确
• std::priority_queue, std::greater> ✅ C++14 起支持透明比较器，也行（但注意类型推导限制）
• std::priority_queue, std::greater> ❌ 缺少模板实参，编译失败
• std::priority_queue, std::greater> ❌ 容器类型不匹配：deque 不满足 RandomAccessIterator，std::greater 内部调用 operator[] 会失败

std::priority_queue, std::greater> min_heap;
min_heap.push(3);
min_heap.push(1);
min_heap.push(4);
// top() == 1，pop 顺序：1 → 3 → 4

自定义类型 + std::greater 的陷阱：它不自动识别你的 operator

std::greater 本质是调用 operator>，不是 operator。如果你只重载了 ，而没写 >，用 std::greater 会编译失败。

• 安全做法：重载 operator>，或
• 更推荐：直接传 lambda 或自定义函数对象，避免依赖全局运算符
• 或者干脆不用 std::greater，改用 std::less 配合反向逻辑（比如存负值）——但这只适用于数值，不通用

struct Task {
    int priority;
    std::string name;
};
// 必须提供 operator> 才能用 std::greater
bool operator>(const Task& a, const Task& b) {
    return a.priority > b.priority; // 注意：这里返回 true 表示 a 优先级更低，所以排在后面
}
std::priority_queue, std::greater> pq;

性能与可读性权衡：lambda 比 std::greater 更灵活但略重

对于简单类型（如 int、double），std::greater 零开销、内联友好；但一旦涉及成员访问或多字段比较，lambda 更直观，且避免污染全局命名空间。

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

• lambda 会生成闭包类型，可能让模板实例化变多，但现代编译器基本优化掉
• 不能用于非类型模板参数（比如某些元编程场景），std::greater 可以
• 调试时 lambda 名称不友好，std::greater 类型名明确

auto cmp = [](const Task& a, const Task& b) { return a.priority > b.priority; };
std::priority_queue, decltype(cmp)> pq(cmp);