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

priority_queue本质是一种**基于堆的容器适配器**,它不会对所有元素全排序,而是始终让“优先级最高”的元素处于队首。比如要快速获取最大/最小值、动态调整元素优先级,优先队列比手动实现堆更简洁,比普通队列更高效。它的核心优势是插入、删除队首元素的时间复杂度均为O(log n),非常适合高频动态优先级场景。
使用前需引入头文件`<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的元素顺序由自定义的优先级规则决定,与插入顺序无关。
世界观察:BIOS怎么设置硬盘启动顺序?电脑BIOS硬盘启动设置方法
天天微速讯:怎么判断笔记本独显坏了?独立显卡坏了的表现
每日速读!WinXP系统打开程序时提示“不是有效的Win32应用程序”怎么办?
环球热门:骁龙860对比骁龙855+哪个值得买?骁龙860对比骁龙855+的介绍
世界微速讯:2020年i5处理器排行榜 i5处理器天梯图排行榜2020
【快播报】Wallpaper怎么取消自动下载 阻止wallpaper自动同步
天天即时:小米CC全新系列发布会在哪看直播?小米CC系列发布会网络直播地址汇总
环球热点!Win2003系统FTP服务器配置教程
环球热点评!喜马拉雅FM和蜻蜓FM哪个好?蜻蜓FM和喜马拉雅FM对比
天天热文:Win7电脑显示蓝屏提示错误代码0X000000EA解决办法