17370845950

优先队列是基于堆的容器适配器，默认大根堆，仅支持push、top、pop等操作；改小根堆需用greater、lambda或自定义比较结构体；不支持遍历、查找、修改中间元素。

优先队列在 C++ 中不是真正意义上的“队列”，而是一个基于堆（默认大根堆）的容器适配器，用来快速获取当前最大（或最小）元素。它底层依赖 vector 和 make_heap 等机制，不支持遍历、查找或修改中间元素，只保证 队首始终是优先级最高者。

基本用法：默认大根堆

默认情况下，priority_queue 是最大堆，顶部元素最大：

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

改成小根堆的三种写法

要让最小元素在顶部，需显式指定比较器。常用方式有：

• 用 greater（需加头文件 ）：
  priority_queue, greater> min_pq;
• 用 lambda（C++20 起支持，但需配合自定义容器类型，较麻烦）
• 写结构体重载 operator()（适合复杂类型）：
  

  struct cmp { bool operator()(int a, int b) { return a > b; } };
  priority_queue, cmp> min_pq;

存自定义类型（比如 pair 或结构体）

只要提供合法的比较逻辑即可。例如按 pair 的 first 升序排列（小顶）：

• 直接用 greater> —— 它按字典序比较，适用于 first 相同时比 second
• 更稳妥的方式是自定义比较器：
  

  auto cmp = [](const pair& a, const pair& b) { return a.first > b.first; };
  priority_queue, vector>, decltype(cmp)> pq(cmp);

注意：自定义比较器必须满足「严格弱序」，且不能用 = 判断相等（应返回 false）。

常见误区和注意事项

优先队列不是万能排序工具，使用时要注意：

• 不支持迭代器遍历：for (auto x : pq) ❌ 编译失败
• 不支持随机访问：pq[0] ❌ 没有下标操作符
• 修改元素后不会自动调整堆：想改某个值？只能 pop 出来、改完再 push 回去（效率低，慎用）
• 底层容器可换，但极少需要：priority_queue> 合法但无实际优势

基本上就这些。用对场景（比如 Top-K、合并 K 个有序链表、Dijkstra 权值更新），它非常高效；乱当普通容器用，反而容易踩坑。