[C++知识库]C++堆/优先队列-STL-priority_queue

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;
    }

};