c++中如何使用priority_queue优先队列_c++优先队列用法

priority_queue 默认是最大堆，顶部元素为最大值；其默认比较器为 std::less，即 a

priority_queue 默认是最大堆还是最小堆

默认是最大堆，也就是顶部元素是最大值。这和很多人直觉相反——以为“优先级高”就该先出小数字，但 C++ 的 priority_queue 模板参数里，第三个比较器默认是 std::less，而 std::less(a, b) 返回 a ，它会让大数“优先级更高”，所以顶部是最大值。

常见错误现象：想实现最小堆却没改比较器，结果 top() 返回最大值，pop() 却删掉了最大值，逻辑全反了。

• 要最小堆：显式传 std::greater，且必须带模板参数（因为 greater 是函数对象模板）
• 自定义类型必须提供 operator 或传自定义比较器，否则编译失败
• 比较器类型必须和容器内元素类型匹配，比如 priority_queue, vector>, greater> 中的 greater 会推导为 greater>，前提是 pair 支持 >（它支持）

声明最小堆的三种写法及区别

最稳妥的是完整写出三个模板参数；C++17 起支持类模板参数推导（CTAD），但 greater 这种占位符写法依赖编译器对空模板参数的推导能力，不同标准库实现可能行为不一致。

priority_queue, greater> min_heap;  // 推荐：明确、兼容性好
priority_queue, greater<>> min_heap2;      // C++14+ 可用，但部分旧 lib 不支持
priority_queue> max_heap;                  // 默认最大堆

注意：vector 不能省略——它是底层容器，不是可推导项；漏掉会编译报错，提示 “no matching constructor”。

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

BibiGPT-哔哔终结者

B站视频总结器-一键总结 音视频内容

下载

自定义结构体怎么进 priority_queue

两种方式：重载 operator，或传 lambda/函数对象（后者需用 decltype 声明类型，较麻烦，一般用前者）。

关键点在于：比较器语义必须是“严格弱序”。如果写成 a.val ，会导致重复元素无法正确排序，甚至死循环。

• 重载 operator 时，返回 a.priority 表示“a 优先级更低”，所以高优先级（数值大）的排前面 → 最大堆
• 若想要最小堆（按 priority 升序），就让 operator 返回 a.priority > b.priority，但这违反直觉，容易出错，不如直接用 greater 配合 priority_queue 声明
• lambda 无法直接作为模板参数（类型不可名状），只能用于 std::make_heap 等算法，不适用于 priority_queue 构造

常见性能与使用陷阱

priority_queue 底层是堆，push() 和 pop() 都是 O(log n)，但不支持查找、修改中间元素、遍历等操作——它不是容器，只是适配器。

• 不要试图用 for (auto x : pq) 遍历：没有迭代器接口，编译失败
• 清空只能反复 pop()，没有 clear() 成员函数；想重用对象又不想手动 pop，可以 swap 一个空队列：pq = decltype(pq)();
• 如果频繁插入后只取 top，且数据量大，考虑是否真需要堆——有时排序后用索引访问更快，特别是静态数据
• 多线程下不安全：没有内置同步，push/top/pop 都需外部加锁

真正容易被忽略的是：它不保证相同优先级元素的入队顺序（不稳定），如果业务依赖 FIFO，得自己在结构体里加序列号字段，并在比较逻辑中兜底。