C++ priority_queue用法详解_C++优先队列自定义排序方法

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++ priority_queue用法详解_C++优先队列自定义排序方法

2025-12-02

浏览次数：次

返回列表

priority_queue是C++中基于堆的容器适配器，默认为大顶堆，可通过自定义比较器实现小顶堆或复杂类型排序，常用于Dijkstra、Huffman等算法。

c++ priority_queue用法详解_c++优先队列自定义排序方法

在C++中，priority_queue 是一个基于堆实现的容器适配器，用于维护一组元素，并始终能够快速访问最大（或最小）元素。默认情况下，它是一个大顶堆，即优先级最高的元素（最大值）位于顶部。

1. priority_queue 基本用法

头文件：

基本声明方式：

priority_queue<int> pq;</int>：存储整数的大顶堆
priority_queue<int vector>, greater<int>> pq;</int></int>：小顶堆

常用操作：

push(x)：插入元素 x
top()：获取堆顶元素（不删除）
pop()：弹出堆顶元素
empty()：判断是否为空
size()：返回元素个数

示例代码：

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

int main() {
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);

    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出：4 3 2 1
        pq.pop();
    }
    return 0;
}

2. 自定义排序：基础结构体

当需要处理复杂类型（如结构体）时，可以通过重载比较函数来自定义优先级规则。

方法一：重载 operator

由于默认使用 less<t></t>，会调用 operator，所以让“优先级高的”返回 false。

struct Student {
    string name;
    int age;
    // 按年龄从小到大排，年龄小的优先级高（小顶堆效果）
    bool operator<(const Student& other) const {
        return age > other.age;  // 注意：这里反着写
    }
};

priority_queue<Student> pq;

注意：operator 返回 true 表示当前对象小于 other。但在大顶堆中，大的在上面。所以为了让年龄小的优先，必须让 age 小的对象“看起来更大”，因此写成 <code>age > other.age。

3. 使用仿函数（Functor）自定义比较器

更清晰的方式是定义一个比较类，实现 operator()。

struct CompareAge {
    bool operator()(const Student& a, const Student& b) const {
        return a.age > b.age;  // 年龄小的优先
    }
};

// 声明时指定第三个模板参数
priority_queue<Student, vector<Student>, CompareAge> pq;

此时，返回 true 表示 a 的优先级低于 b，即 b 应该排在前面。这和 sort 的比较函数逻辑一致：true 表示需要交换。

常见错误：误以为返回 true 是“优先”，实际上在 priority_queue 中，比较器的作用是判断谁该被放在下面。如果 cmp(a,b)==true，说明 a 的优先级比 b 低，b 应该浮到上面。

4. 使用 lambda 表达式？不行！但可以用 decltype 配合函数对象

不能直接在模板参数中使用 lambda，但可以配合 decltype 和构造函数使用：

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

注意：这里必须把 cmp 作为参数传入构造函数，否则无法推导行为。

适用场景：比较逻辑复杂且只在局部使用时，这种方式更灵活。

5. 常见应用场景

Dijkstra 算法：取出距离最小的节点
Huffman 编码：合并频率最小的两棵树
合并多个有序链表：用小顶堆维护每个链表的当前头节点
滑动窗口最大值：可用 priority_queue 辅助实现

例如：Dijkstra 中通常这样定义：

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 或者自定义比较器，按距离排序

基本上就这些。关键点是理解默认是大顶堆，自定义比较器时要明确“谁优先谁靠上”，返回 true 表示第一个参数优先级更低。不复杂但容易忽略细节。

以上就是C++ priority_queue用法详解_C++优先队列自定义排序方法的详细内容，更多请关注其它相关文章！

# 多个 # 江干区网站优化推广服务 # 网络营销大面积推广 # 掇刀seo优化口碑好 # 无锡网站建设优化技术 # 绥德关键词排名优化软件 # 商丘seo网站优化推荐 # 关键词快速排名软件 # 铁岭本地网站建设流程 # 网站推广是什么技术 # 湖南网站建设怎么样 # 更大 # 可以用 # 编码 # 第一个 # 放在 # 链表 # 是一个 # 返回值 # 如何使用 # 自定义 # stream # ios # c++ # ai

相关栏目：【科技资讯46185 】【网络学院92790 】

上一篇：如何在CSS中实现文字渐变_hover状态动态变化

下一篇：html游戏怎么运行_运行html游戏方法及注意事项【教程】

首页

关于我们

产品展示

咨询研究

新闻中心

留言板

联系我们

新闻中心 NEWS CENTER

C++ priority_queue用法详解_C++优先队列自定义排序方法

1. priority_queue 基本用法

2. 自定义排序：基础结构体

3. 使用仿函数（Functor）自定义比较器

4. 使用 lambda 表达式？不行！但可以用 decltype 配合函数对象

5. 常见应用场景