# 优先队列priority_queue

#include <queue>

提供常数时间的最大元素查找,对数时间的插入与提取,底层原理是二叉堆

# 1. 常用方法

# 构造

priority_queue<类型,容器,比较器>pque

  • 类型:要储存的数据类型

  • 容器:储存数据的底层容器,默认为 vector<类型>,竞赛中保持默认即可

  • 比较器:比较大小使用的比较器,默认为less<类型>,可自定义

//储存int的大顶堆
priority_queue<int> pquel; // 默认大顶堆
priority_queue<int, vector<int>, greater<int>> pque2;// 储存int的小顶堆,greater<int>控制
1
2
3

对于需要自定义比较器的情况,涉及一些初学时容易看迷糊的语法(重载小括号运算符/ambda 表达式),在此就不展开讲了。如 果想要了解,可以查阅 cppreference (opens new window) 中的代码示例。

# 其他

作用 用法 示例
进堆 .push(元素) que.push(1);
出堆 .pop() que.pop();
取堆顶 .top() int a= que.top();
查看大小/判空

进出队复杂度 O(logn)O(log n),取堆顶$ O(1)$.

# 2. 适用情形

持续维护元素的有序性:每次向队列插入大小不定的元素,或者每次从队列里取出大小最大/最小的元素,元素数量n,插入操作数量k

  • 每次插入后进行快速排序:knlognk\cdot n\log n
  • 使用优先队列维护:klognk\cdot\log n

# 3. 注意事项

# 仅堆顶可读

只可访问堆顶,其他元素都无法读取到。下面是错误用法

cout << pque[1] <<  endl;
1

# 所有元素不可写

堆中所有元素是不可修改的。下面是错误用法

pque[1] = 2;
pque.top() = 1;
1
2

如果恰好要修改的是堆顶元素,则可以通过以下完成:

int tp = pque.top(); //先将堆顶取出来,存在tp里
pque.pop(); //再弹出堆顶
pque.push(tp+1); //最后将修改的tp再压入堆里,此时不一定再是堆顶,因为 只有大顶堆和小顶堆
1
2
3
上次更新时间:: 2/16/2025, 12:37:58 AM