C++ priority_queue优先队列怎么实现小顶堆-C++-PHP中文网

c++oding="utf-8" ?>

默认是大顶堆，改小顶堆需显式指定std::greater为第三个模板参数；自定义类型须提供按“大于”语义的比较器；容器必须用vector，不可换deque或list。

c++ priority_queue优先队列怎么实现小顶堆

默认是大顶堆，怎么改成小顶堆

priority_queue 默认用 std::less 比较器，底层是大顶堆（最大元素在队首）。要变成小顶堆，必须显式指定比较逻辑——不是改数据，而是换比较方式。

最常用、最直接的做法是用 std::greater 作为第三个模板参数：

std::priority_queue<int std::vector>, std::greater<int>> min_heap;</int></int>

注意：第二个参数 std::vector<int></int> 不能省略，即使你只改第三个参数。因为模板参数顺序固定，跳过中间会导致编译错误。

自定义类型的小顶堆怎么写比较器

对结构体或类，std::greater 不会自动生效，必须提供可调用的比较逻辑。推荐用 lambda（C++20 起支持）或仿函数，但更稳妥的是重载 operator 并「反向使用」——因为 priority_queue 默认用 <code> 做“小于”判断，而它建的是大顶堆；所以如果你希望小值优先，就得让 <code>a 在逻辑上表示“a 应该排在 b 后面”，也就是实际按「大于」语义比较。

更清晰的做法是显式传入自定义比较器：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

struct Node {
    int val;
    int id;
};
// 小顶堆：val 小的优先
auto cmp = [](const Node& a, const Node& b) { return a.val > b.val; };
std::priority_queue<node std::vector>, decltype(cmp)> min_heap(cmp);</node>

lambda 必须捕获为空（否则 decltype(cmp) 类型不可默认构造），且不能含外部变量
如果用类仿函数，要确保有默认构造函数，否则 priority_queue 初始化失败
不要试图只重载 operator>——priority_queue 只认 operator 或你传入的 Compare callable

为什么用 vector 作容器，不能换成 deque 或 list

std::priority_queue 的底层容器必须支持随机访问迭代器和 push_back()/pop_back()，还要能高效地做堆操作（如 make_heap）。std::vector 满足全部要求；std::deque 理论上也支持随机访问，但部分标准库实现（如 libstdc++）在堆算法中硬编码依赖了 vector 的连续内存特性，用 deque 可能编译失败或行为未定义；std::list 连随机访问都没有，直接不合法。

所以即使你只想要小顶堆，容器参数仍得写 std::vector<t></t>，别想着换。

常见翻车点：初始化后修改比较逻辑？

不行。priority_queue 的比较器在构造时绑定，之后无法更换。比如你写了：

auto cmp1 = [](auto& a, auto& b) { return a > b; };
std::priority_queue<int vector>, decltype(cmp1)> q1(cmp1);
// 下面这行是错的：q1 的比较器已固定，不能 runtime 替换
q1 = std::priority_queue<int vector>, std::greater<int>>(); // 类型不兼容</int></int></int>

如果需要动态切换大小顶堆逻辑，得用两个独立队列，或改用 std::make_heap + std::vector 手动管理。

还有人误以为 push 时传比较器能临时改变行为——push() 没有比较器参数，所有元素都走同一个预设逻辑。