c++中priority_queue怎么使用_priority_queue优先级队列用法详解-C++-PHP中文网

c++中priority_queue怎么使用_priority_queue优先级队列用法详解

穿越時空

发布： 2025-09-30 19:05:02

原创

698人浏览过

priority_queue是C++中基于堆的容器适配器，默认为大根堆，定义在queue头文件中，支持push、pop、top等操作；通过std::greater可实现小根堆；自定义类型需重载<或传入比较函数对象；常用于Dijkstra、合并K个有序链表等场景。

c++中priority_queue怎么使用_priority_queue优先级队列用法详解

在C++中，priority_queue 是一个基于堆结构实现的容器适配器，用于自动维护元素的优先级顺序。默认情况下，它是一个大根堆，即队头始终是当前最大的元素。它定义在 queue 头文件中，使用非常方便，适用于需要动态管理优先级的场景，比如Dijkstra算法、合并K个有序链表等。

基本用法与定义

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

#include <queue>

最简单的定义方式如下：

std::priority_queue<int> pq;

这创建了一个存储整数的大顶堆。插入和访问元素的方法如下：

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

pq.push(x)：将元素 x 插入队列，自动调整堆结构。
pq.pop()：移除堆顶（最大值），不返回值。
pq.top()：返回堆顶元素（最大值）。
pq.empty()：判断队列是否为空。
pq.size()：返回元素个数。

示例代码：

std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
// 输出：30 20 10

小根堆的实现

默认是大根堆，如果需要小根堆（最小值在顶部），可以通过指定比较函数来实现。常用方法是使用 std::greater：

MagicStudio

图片处理必备效率神器！为你的图片提供神奇魔法

102

查看详情

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

此时插入相同数据：

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

注意模板参数顺序：

第一个：元素类型（如 int）
第二个：底层容器类型，默认是 vector，通常不需要改
第三个：比较类，决定排序规则

自定义类型与比较规则

当处理结构体或类时，需要自定义比较逻辑。有两种常见方式：

方法一：重载操作符 <

struct Person {
    int age;
    std::string name;
    bool operator<(const Person& p) const {
        return age < p.age; // 年龄大的优先级高
    }
};
std::priority_queue<Person> pq;

方法二：传入仿函数或lambda（推荐用于复杂逻辑）

auto cmp = [](const Person& a, const Person& b) {
return a.age < b.age; // 小顶堆按年龄升序
};
std::priority_queue<Person, std::vector<Person>, decltype(cmp)> pq(cmp);

注意：这里需要把比较函数对象传给构造函数，否则会出错。