C++中的std::priority_queue是什么？（如何实现自定义优先级的堆）-C++-PHP中文网

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

std::priority_queue默认是最大堆，顶部元素为最大值；要最小堆需显式指定std::greater等比较器并补全容器类型；不支持修改堆中单个元素，无clear()函数，清空应swap。

c++中的std::priority_queue是什么？（如何实现自定义优先级的堆）

默认是最大堆，顶部元素是最大值。它底层用 std::vector 存储，配合 std::make_heap 等算法维护堆序，但你不能直接访问底层容器的顺序——这是封装设计决定的。

常见错误现象：写 std::priority_queue q; 后反复 q.top()，发现取出来的是越来越小的数，误以为“它在降序弹出”，其实只是每次弹出当前最大值，不是排序迭代器。

要最小堆，必须显式传入比较器：std::priority_queue, std::greater>
不能只改第三个模板参数而漏掉第二个（容器类型），否则编译失败：std::priority_queue> 是错的
std::less 和 std::greater 都要求操作符重载可用；自定义类型若没定义 operator，得自己写仿函数或 lambda（但 lambda 不能作模板参数，得用 decltype + 变量捕获，稍麻烦）

核心是提供一个满足 Strict Weak Ordering 的比较逻辑。别直接 return a.score > b.score —— 这不满足可传递性约束，可能触发未定义行为。

正确做法是把逻辑“翻译”成 operator 的语义：让 a 返回 true 当且仅当 a 应该排在 b 后面（即 b 优先级更高）。因为 std::priority_queue 默认用 std::less，也就是按“小于”关系建最大堆。

或者封装成仿函数类，更清晰：

struct Compare {
    bool operator()(const Node& a, const Node& b) {
        if (a.score != b.score) return a.score  b.id; // id 小的优先
    }
};

然后声明：std::priority_queue, Compare>

因为它不提供任何接口定位、更新或修复单个元素的堆序。底层容器虽可访问（通过继承或友元 hack），但公开 API 完全禁止随机修改——一旦改了某个元素值，堆结构就坏了，top() 可能返回错误结果，pop() 可能崩溃。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

使用场景：如果你需要增删改查+动态调整优先级（比如 Dijkstra 中更新节点距离），std::priority_queue 不适合。此时应换用支持 decrease-key 的数据结构，例如：

性能影响：用 std::set 替代，单次“更新”变成 O(log n) 插入 + O(log n) 删除，比真正 decrease-key 的 O(1) 摊还代价高，但通常够用。

看起来安全，但要注意：它不保证线程安全。多个线程同时调用 push() 和 size()，size() 返回值可能立刻过期，甚至引发数据竞争（尤其在 debug 模式下可能触发断言）。

不要用 while (!q.empty()) { auto x = q.top(); q.pop(); ... } 在多线程里裸写——empty() 和 top() 之间可能被其他线程 pop 掉，导致 top() 调用未定义行为
正确做法是先 top() 再 pop()，或用锁保护整个操作序列
另外：size() 返回 size_type（通常是 size_t），和 int 混用可能触发隐式转换警告，尤其在 64 位系统上