c++中priority_queue怎么使用_C++ priority_queue优先队列使用指南

优先队列默认为最大堆，可通过greater或自定义比较实现最小堆，支持高效插入和弹出操作，适用于贪心、Dijkstra等算法。

在c++中，priority_queue 是一个非常实用的容器适配器，用于实现优先队列。它默认基于堆结构（通常是最大堆），可以自动将元素按优先级排序，每次取出的都是当前优先级最高的元素。

1. 包含头文件与基本定义

使用 priority_queue 需要包含头文件 <queue>：

#include <queue>
#include <iostream>
using Namespace std;

最基本的定义方式如下：

priority_queue<int> pq; // 默认是最大堆

此时，较大的数值优先级更高，top() 返回最大值。

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

2. 常用操作方法

priority_queue 支持以下常用接口：

• push(x)：插入元素 x
• pop()：移除顶部元素（最高优先级）
• top()：访问顶部元素，不删除
• empty()：判断队列是否为空
• size()：返回元素个数

示例代码：

priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);

while (!pq.empty()) {
   cout << pq.top() << " "; // 输出：30 20 10
   pq.pop();
}

3. 使用最小堆（小顶堆）

默认是最大堆，若想使用最小堆，需指定比较方式：

priority_queue<int, vector<int>, greater<int>> min_pq;

这里三个模板参数分别为：

AppMall应用商店

AI应用商店，提供即时交付、按需付费的人工智能应用服务

56

查看详情

• 元素类型（int）
• 底层容器（通常用 vector）
• 比较函数对象（greater 表示小的优先）

示例：

min_pq.push(10);
min_pq.push(30);
min_pq.push(20);

while (!min_pq.empty()) {
   cout << min_pq.top() << " "; // 输出：10 20 30
   min_pq.pop();
}

4. 自定义比较规则（结构体/类）

对于复杂类型（如结构体），可以通过重载操作符或自定义比较函数来设定优先级。

方式一：重载 operator<（适用于最大堆）

Struct Person {
   String name;
   int age;
   bool operator<(const Person& p) const {
      return age < p.age; // 年龄大的优先
   }
};

priority_queue<Person> pq;
pq.push({"Alice", 25});
pq.push({"Bob", 30});
cout << pq.top().name; // 输出 Bob

方式二：自定义比较结构体（更灵活）

struct Compare {
   bool operator()(const Person& a, const Person& b) {
      return a.age < b.age; // 最大堆：年龄大的优先
   }
};

priority_queue<Person, vector<Person>, Compare> pq;

如果想按年龄小的优先：

return a.age > b.age; // 实现最小堆效果

基本上就这些。掌握 priority_queue 能显著提升处理调度、贪心、Dijkstra 等算法的效率。注意它不支持遍历和迭代器，但插入和弹出都是 O(log n) 时间复杂度，非常高效。