C++中的priority_queue是基于堆实现的容器适配器，默认为大根堆，提供push、pop、top等操作，时间复杂度为O(log n)，可通过std::greater或自定义比较器实现小根堆或自定义优先级，适用于Dijkstra、任务调度等场景。
C++ 中的 priority_queue 是一个基于堆结构实现的容器适配器，用于快速获取最大（或最小）元素。它默认是一个大根堆，即队头始终是当前优先级最高的元素。本文将介绍它的基本用法、底层实现原理以及如何使用自定义比较器。
基本用法与常见操作
priority_queue 定义在 queue 头文件中，使用方式如下：
#include #include // 默认大根堆std::priority_queue pq;pq.push(10);pq.push(30);pq.push(20);std::cout << pq.top(); // 输出 30pq.pop();std::cout << pq.top(); // 输出 20
常用成员函数包括：
push(x)：插入元素 x pop()：移除堆顶元素 top()：访问堆顶元素（不删除） empty()：判断是否为空 size()：返回元素个数
底层实现原理
priority_queue 底层基于 堆（heap） 实现，通常使用 vector 或 deque 作为存储结构。标准库通过 make_heap、push_heap 和 pop_heap 等算法维护堆性质。
立即学习“C++免费学习笔记（深入）”；
每次 push 操作会将元素插入尾部，然后向上调整（上浮）以保持堆序；pop 则将首尾交换后弹出，并向下调整（下沉）恢复堆结构。这两个操作的时间复杂度均为 O(log n)。
由于 priority_queue 是容器适配器，不能直接遍历，也不提供迭代器。
自定义比较器
默认情况下，priority_queue 使用 std::less 构造大根堆。若要改为小根堆，可指定比较器为 std::greater：
std::priority_queue<int, std::vector, std::greater> min_pq;min_pq.push(10);min_pq.push(5);min_pq.push(15);std::cout << min_pq.top(); // 输出 5
对于自定义类型（如结构体），可以重载比较函数或传入函数对象：
struct Person { int age; std::string name;};// 方式一：重载 operator<bool operator<(const Person& a, const Person& b) { return a.age < b.age; // 年龄大的优先}std::priority_queue pq;pq.push({25, "Alice"});pq.push({30, "Bob"});std::cout << pq.top().name; // 输出 Bob
也可以使用 lambda 表达式配合函数对象（需用 decltype 并传入构造参数）：
auto cmp = [](const Person& a, const Person& b) { return a.age < b.age; // 小根堆逻辑：年龄小的优先};std::priority_queue<Person, std::vector, decltype(cmp)> pq(cmp);
基本上就这些。掌握 priority_queue 的使用和比较器设计，能有效应对涉及优先级调度、Dijkstra 算法、合并 K 个有序链表等典型问题。理解其堆基础也有助于分析性能和调试行为。
以上就是C++ priority_queue怎么用_C++优先队列底层实现与自定义比较器的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486776.html
微信扫一扫 
支付宝扫一扫 
