优先队列基于堆实现，默认为大根堆，包含于queue头文件中。使用std::priority_queue<int>声明，默认提供push、top、pop等操作。通过greater<int>可创建小根堆：priority_queue<int, vector<int>, greater<int>>。自定义类型需重载<或定义比较结构体。常用于Top K、Dijkstra、合并K链表等场景。

在C++中，优先队列（priority_queue）是一种基于堆结构实现的容器适配器，能够自动将元素按优先级排序，默认情况下是大根堆，即最大元素始终位于队首。它定义在 queue 头文件中，使用非常方便，适用于需要动态维护最大值或最小值的场景，比如Dijkstra算法、合并K个有序链表等。

1. 基本用法与定义

要使用 priority_queue，需包含头文件：

#include <queue>

基本声明方式如下：

std::priority_queue<int> pq; // 默认大顶堆，最大的元素在顶部

插入和访问元素的操作：

立即学习“”；

• pq.push(x)：插入元素 x
• pq.top()：获取堆顶元素（最高优先级）
• pq.pop()：删除堆顶元素
• pq.empty()：判断是否为空
• pq.size()：返回元素个数

示例代码：

#include <tream>
#include <queue>
using namespace std;

while (!pq.empty()) {
cout << pq.top() << ” “; // 输出: 30 20 10
pq.pop();
}
return 0;
}

2. 使用小根堆（最小堆）

默认是大根堆，若想让最小元素在顶部，可以指定比较方式。C++ 提供了 greater 比较器：

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

说明：

数据为基，先见未见

95

• 第一个参数：元素类型
• 第二个参数：底层容器，通常为 vector<int>
• 第三个参数：比较函数对象，greater<int> 表示小顶堆

示例：

priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(20);

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

3. 自定义数据类型与比较规则

如果要存储自定义结构体，比如任务优先级，就需要重载比较规则。有两种常用方法：

方法一：重载操作符 <

struct Task {
int priority;
string name;
bool operator<(const Task& t) const {
return priority < t.priority; // 优先级高的排前面（大根堆）
}
};

priority_queue<Task> task_pq;

方法二：自定义比较结构体

struct Compare {
bool operator()(const Task& a, const Task& b) {
return a.priority < b.priority; // 大根堆
}
};

priority_queue<Task, vector<Task>, Compare> task_pq;

注意：在 priority_queue 中，比较函数的作用是判断哪个元素“更小”，因此如果返回 true，表示 a 应该比 b 后弹出（即 a 优先级低）。

4. 常见应用场景

优先队列常用于以下问题：

• 求前 K 大/小的元素（Top K 问题）
• 合并 K 个有序链表
• Dijkstra 最短路径算法
• 哈夫曼
• 任务调度系统

例如，求一个数组中最大的 K 个数，可以用小根堆维护大小为 K 的堆，遍历数组不断更新堆顶。

基本上就这些。掌握构造方式、自定义比较和基本操作，就能灵活使用 priority_queue 解决多数问题。

以上就是++如何使用优先队列(priority_queue)_C++堆结构与优先队列用法详解的详细内容，更多请关注php中文网其它相关文章！