c++如何使用优先队列(priority_queue)_C++堆结构与优先队列用法详解-C++-PHP中文网

c++如何使用优先队列(priority_queue)_C++堆结构与优先队列用法详解

冰火之心

发布： 2025-11-05 22:24:02

原创

824人浏览过

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

c++如何使用优先队列(priority_queue)_c++堆结构与优先队列用法详解

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

1. 基本用法与定义

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

#include <queue>

基本声明方式如下：

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

插入和访问元素的操作：

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

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

示例代码：

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

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

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;

说明：

先见AI

数据为基，先见未见

查看详情

第一个参数：元素类型
第二个参数：底层容器，通常为 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 优先级低）。