priority_queue是什么?C++ priority_queue怎么使用?

程序员必懂:C++优先队列priority_queue的核心用法

在算法面试、竞赛编程中,“高效排序”是高频考点,而C++标准库中的priority_queue(优先队列)正是解决“动态优先级调度”类问题的利器——它既能实现堆排序的核心逻辑,又能简化代码实现,堪称算法题中的“效率神器”。

priority_queue是什么?C++ priority_queue怎么使用?

什么是priority_queue?

priority_queue本质是一种**基于堆的容器适配器**,它不会对所有元素全排序,而是始终让“优先级最高”的元素处于队首。比如要快速获取最大/最小值、动态调整元素优先级,优先队列比手动实现堆更简洁,比普通队列更高效。它的核心优势是插入、删除队首元素的时间复杂度均为O(log n),非常适合高频动态优先级场景。

C++中priority_queue的基础使用

使用前需引入头文件`<queue>`,其模板定义为:`template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>> class priority_queue`。

默认情况下,它是**大顶堆**(队首为最大元素),示例代码如下: cpp #include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq; // 默认大顶堆 pq.push(3); pq.push(1); pq.push(5); cout << pq.top(); // 输出5(最大元素) pq.pop(); // 删除队首元素5 cout << pq.top(); // 输出3 return 0; }

若需**小顶堆**(队首为最小元素),只需修改第三个模板参数为`greater<int>`: cpp priority_queue<int, vector<int>, greater<int>> pq_min;

自定义优先级的高级用法

当元素是结构体或类,需自定义排序规则时,可通过仿函数(函数对象)实现。比如按学生分数从高到低排序: cpp struct Student { int score; string name; }; // 自定义仿函数:分数高的优先级高 struct CompareStudent { bool operator()(const Student& a, const Student& b) { return a.score < b.score; // 分数小的排后面 } }; int main() { priority_queue<Student, vector<Student>, CompareStudent> pq; pq.push({90, "张三"}); pq.push({95, "李四"}); cout << pq.top().name; // 输出李四(分数最高) return 0; }

相关问题及解答

1. 问:priority_queue的默认容器是什么?为什么用它? 答:默认容器是vector,因为vector支持随机访问,便于堆的调整(堆操作需通过索引定位父子节点),且空间分配灵活。

2. 问:priority_queue支持修改中间元素的优先级吗? 答:不支持。若需修改,需先删除旧元素,再插入新元素(可借助辅助容器标记无效元素,避免频繁重建堆)。

3. 问:它和普通队列的核心区别是什么? 答:普通队列遵循FIFO(先进先出),元素顺序由插入顺序决定;而priority_queue的元素顺序由自定义的优先级规则决定,与插入顺序无关。

推荐DIY文章
PC上近几年有什么必玩的3A游戏?《刺客信条:影》推荐解析
卡西欧MR-G三十周年【悠】系列腕表 限定发售
IC行业龙头云集!300场演讲,ICCAD-Expo即将在京启幕
海信小墨E5S Pro成双11全网超级大单品,RGB-Mini LED引领大屏换代趋势
双11战报出炉!海信电视包揽行业销量、销额双第一
类似加勒比海盗的游戏,单人玩家最值得入的三款
精彩关注