C++如何使用priority_queue_C++优先队列容器与应用示例

priority_queue是C++ STL中基于堆的容器适配器，默认为最大堆，常用于任务调度、Dijkstra算法等场景。1. 基本用法：包含头文件，定义方式有priority_queue pq（最大堆）和priority_queue pq（最小堆），常用操作包括push、pop、top、empty和size。示例输出为30 20 10。2. 自定义比较：可通过重载operator

在C++中，priority_queue 是标准模板库（STL）提供的一个容器适配器，用于实现优先队列。它基于堆结构，默认情况下使用最大堆，即每次取出的元素是当前队列中最大的。它常用于需要按优先级处理数据的场景，比如任务调度、Dijkstra最短路径算法等。

1. priority_queue的基本用法

头文件： 使用 #include 即可引入 priority_queue。

定义方式：

• priority_queue pq;：默认最大堆，顶部是最大值。
• priority_queue, greater> pq;：最小堆，顶部是最小值。

常用操作：

• pq.push(x)：插入元素 x。
• pq.pop()：移除顶部元素（不返回）。
• pq.top()：获取顶部元素。
• pq.empty()：判断是否为空。
• pq.size()：返回元素个数。

示例代码：

#include 
#include 
using namespace std;
int main() {
priority_queue pq;
pq.push(10);
pq.push(30);
pq.push(20);
while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
}
// 输出：30 20 10
return 0;
}

2. 自定义比较函数（结构体或类）
当需要处理自定义类型（如结构体）时，可以通过重载比较运算符或提供比较类来定义优先级规则。
方法一：重载 operator
struct Person {
    string name;
    int age;
    Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& p) const {
    return age < p.age; // 年龄大的优先级高（最大堆）
}
};
priority_queue pq;
pq.push(Person("Alice", 25));
pq.push(Person("Bob", 30));
cout 
方法二：自定义比较结构体
struct CompareAge {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age; // 最大堆
    }
};
priority_queue, CompareAge> pq;
若想实现年龄小的优先，则改为：a.age > b.age，即可变为最小堆逻辑。
3. 实际应用示例：合并K个有序链表
LeetCode经典题：使用 priority_queue 维护每条链表当前最小节点，每次取出最小值节点加入结果链表。
#include 
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
struct Compare {
bool operator()(ListNode a, ListNode b) {
return a->val > b->val; // 最小堆：值小的优先
}
};
ListNode mergeKLists(vector>& lists) {
priority_queue, vector>, Compare> pq;
for (ListNode* head : lists) {
    if (head) pq.push(head);
}

ListNode dummy(0);
ListNode* tail = &dummy;

while (!pq.empty()) {
    ListNode* node = pq.top(); pq.pop();
    tail->next = node;
    tail = tail->next;
    if (node->next) pq.push(node->next);
}

return dummy.next;
}

该方法时间复杂度为 O(N log k)，其中 N 是所有节点总数，k 是链表数量，效率较高。
4. 注意事项与常见问题


priority_queue 不支持遍历，只能访问 top 元素。
修改已有元素会破坏堆结构，应避免。
如果需要动态更新优先级，考虑使用 set 或手写堆。
注意自定义比较函数的逻辑方向，greater 表示“更小的优先”，即最小堆。

基本上就这些。掌握 priority_queue 能显著简化很多算法设计，特别是在贪心和图算法中非常实用。熟悉其接口和自定义方式后，使用起来很高效。
		


# c++ 
# node 
# ai 
# ios 
# stream 
# 常见问题 
# 运算符 
# 比较运算符 
# include 
# 结构体 
# int 
# 接口 
# 堆 
# operator 
# 算法 
# leetcode 
# 自定义 
# 大堆 
# 链表 
# 最小值 
# 头文件 
# 是在 
# 已有 
# 遍历 
# 较高 
# 很高 
 




相关栏目：
    【
        Google疑问12    】
    【
        Facebook疑问10    】
    【
        网络优化76771    】
    【
        技术知识130152    】
    【
        IDC云计算60162    】
    【
        营销推广131313    】
    【
        AI优化88182    】
    【
        百度推广37138    】
    【
        网站推荐60173    】
    【
        精选阅读31334    】




相关推荐：
C++如何使用std::async进行异步编程？（future用法） 
C++如何编写函数模板？（泛型编程入门） 
Mac版Final Cut Pro入门_Mac视频剪辑基础操作【教程】 
php8.4xdebug无法调试怎么办_php8.4xdebug配置问题解决【解答】 
VSC怎么配置PHP的Xdebug_远程调试设置步骤【详解】 
Win11玩游戏全屏闪退怎么办_Win11全屏优化禁用设置【教程】 
php本地部署支持nodejs吗_php与nodejs混合开发环境搭建教程【教程】 
Win11怎么激活Windows10_Win11激活Win10系统方法【步骤】 
Python项目维护经验_长期演进说明【指导】 
MAC怎么使用表情符号面板_MAC Emoji快捷键调用与符号查找【方法】 
php8.4新语法match怎么用_php8.4match表达式替代switch【方法】 
php删除数据怎么清空表_truncate与delete区别及用法【汇总】 
c++如何利用doxygen生成开发文档_c++ 代码注释规范与HTML文档导出【案例】 
Mac上的iMovie如何剪辑视频？（新手入门教程） 
Win11如何更改用户账户文件夹名称 Win11修改C:Users用户名【终极教程】 
如何在Golang中引入测试模块_Golang测试包导入与使用实践 
c++中如何求一个数的平方根_c++ sqrt函数与牛顿迭代法 
Win11相机打不开提示错误怎么修_相机权限开启与驱动修复【影像修复】 
如何使用 Python 合并文件夹内多个 Excel 文件并避免权限错误 
Mac如何查看电池健康百分比_Mac系统信息电源检测 
Win11怎么关闭内容自适应亮度_Windows11显示设置CABC关闭 
Win11如何设置系统声音_Win11系统声音调整教程【攻略】 
Win11怎么连接投影仪_Win11多显示器投屏设置指南【步骤】 
C++如何解析JSON数据？（nlohmann/json库示例） 
微信短链接怎么还原php_用浏览器开发者工具抓包获取【方法】 
mac怎么查看wifi密码_MAC查看已连接WiFi密码方法【技巧】 
全球各国上班时间表外贸邮件时间 
Win11怎么看电池循环次数_Win11笔记本电池寿命检测【命令】 
如何使用Golang读取日志文件_Golang bufio Scanner日志处理示例 
Win11怎么更改系统语言_Win11中文语言包下载与安装【指南】 
Python lxml的etree和ElementTree有什么区别 
使用类变量定义字符串常量时的类型安全最佳实践 
mac怎么看硬盘大小_MAC查看磁盘存储空间与文件占用【详解】 
Win11怎么设置默认浏览器Chrome_Windows11修改默认网页打开方式 
如何在Golang中实现服务熔断与限流_Golang微服务容错与流控方法 
php怎么连接数据库_MySQL数据库连接的基础代码编写【说明】 
Win11怎么修改DNS服务器 Win11设置DNS加速网络【指南】 
Win10怎么创建桌面快捷方式 Win10为应用创建快捷方式【步骤】 
Python类装饰器使用_元编程解析【教程】 
Windows怎样关闭开始菜单推荐广告_Windows关闭开始菜单推荐设置【步骤】 
LINUX如何查看文件类型_Linux中file命令的识别与应用 
如何使用Golang实现基本类型比较_Golang比较操作符使用方法 
Win11怎么更改任务栏位置_修改注册表将Win11任务栏置顶【教程】 
英国搜索：多数英国人认为语言搜索是未来搜索 
c++的mutex和lock_guard如何使用 互斥锁保护共享资源【多线程】 
c++中如何进行二进制文件读写_c++ read与write函数用法 
Python字符串操作教程_切片拼接与格式化详解 
如何在Golang中实现微服务负载均衡_Golang负载均衡策略与实现示例 
PHP 中如何在函数内持久化修改引用变量的指向 
Python网页解析流程_html结构说明【指导】 


		
 2025-11-20