C++如何使用优先队列（priority_queue）？（堆数据结构）

C++中priority_queue默认为最大堆，top()返回最大元素；要实现最小堆需指定std::greater比较器；仅支持堆顶访问和增删，不支持遍历与修改。

在C++中，priority_queue 是标准模板库（STL）提供的**最大堆**实现，默认按元素值从大到小自动排序。它底层基于堆（通常是二叉堆），支持在 O(log n) 时间内插入和弹出最值元素。

基本用法与默认行为

默认情况下，priority_queue 是一个**最大堆**，顶部（top()）返回最大元素：

• 声明：std::priority_queue pq;
• 插入：pq.push(3); pq.push(1); pq.push(4);
• 访问顶部：pq.top() → 返回 4（不删除）
• 弹出顶部：pq.pop(); → 移除 4，之后 top() 变为 3
• 判空：pq.empty()，获取大小：pq.size()

如何创建最小堆？

要让 priority_queue 表现为**最小堆**（顶部是最小元素），需显式指定比较器：

• 使用 std::greater：std::priority_queue, std::greater> min_pq;
• 等价写法（更直观）：std::priority_queue, std::less> 是默认最大堆；std::greater 翻转逻辑，使小的元素“优先”上浮
• 自定义类型时，可传入 lambda（C++20 起支持）或仿函数，例如：auto cmp = [](const Node& a, const Node& b) { return a.cost > b.cost; };，然后声明为 priority_queue, decltype(cmp)> pq(cmp);

常用操作与注意事项

priority_queue 不提供遍历、查找或随机访问接口，仅支持堆顶操作和增删：

• 没有 begin()/end()，不能用范围 for 遍历内部元素
• 不支持修改已有元素——若需更新优先级（如 Dijkstra 中的减小键），应插入新元素并配合标记/懒删除（例如记录已处理节点，遇到旧版本直接跳过）
• 底层容器默认是 std::vector，也可换为 std::deque（需显式指定，但极少必要）
• 构造时可传入迭代器区间，自动建堆：priority_queue pq(v.begin(), v.end());

典型应用场景举例

优先队列天然适合需要动态维护“当前最优选择”的问题：

• Top-K 问题：维护大小为 K 的最小堆，遍历数据流，比堆顶大就替换，最后堆中即为最大的 K 个数
• Huffman 编码：每次合并频率最小的两个节点，用最小堆高效取最小
• Dijkstra 算法：优先取出当前距离最小的未访问节点，配合懒删除避免重复处理
• 任务调度：按优先级或截止时间排序，高优任务先执行

基本上就这些。用对比较器，理解它是只读顶+单向弹出的结构，就不容易踩坑。