admin管理员组文章数量:1624333
1.头文件:
#include<queue>
2.定义:
priority_queue<int>a;
(这是最简单的形式,省略了另外两个参数)(同时此写法默认a为大顶堆)
何为大顶堆?
可以理解为每次入队自动将最大值放在队顶
3.详细定义:
priority_queue<Type, Container, Functional>
(Type为数据类型, Container为保存数据的容器,Functional为元素比较方式。)
如果不写后两个参数,则第二个参数默认为vector容器,第三个参数默认为大顶堆
priority_queue <int,vector<int>,greater<int> > q;//小顶堆(小的元素在堆顶)
priority_queue <int,vector<int>,less<int> >q;//大顶堆(大的元素在堆顶)
以上为小顶堆和大顶堆的定义方式
4.基本操作
top 返回队头元素
push 插入元素
pop 删除元素
empty 队列是否为空
size 返回队列内元素个数
emplace 原地构造一个元素并插入队列
swap 交换内容
5.例子:
这是力扣上的一题
思路:路上的不是加油站,而是一桶桶的油,每次经过的时候,就把油带上,当油不够的时候我们就取身上最大的那桶油加上,这样如果身上没油了,那么就到不了了
实现:每次经过加油站时,把油量加入循环队列中:
class Solution {
public:
int minRefuelStops(int target, int cur, vector<vector<int>> s) {
int i = 0, res;
priority_queue<int>pq;
for (res = 0; cur < target; res++) {
while (i < s.size() && s[i][0] <= cur)
pq.push(s[i++][1]);
if (pq.empty()) return -1;
cur += pq.top(), pq.pop();
}
return res;
}
};
本文标签: 队列stlpriorityqueue
版权声明:本文标题:C++堆优先队列-STL-priority_queue 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728896087a1178425.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论