c++优先队列（priority_queue）小顶堆 大顶堆_priority_queue默认大顶堆

写到力扣滑动窗口的最大值其中有一个解法是靠优先队列解题，前来记录总结一下

priority——queue

实际上是一个heap，是一个拥有权值观念的queue，它允许在底端添加元素，顶端去除元素，删除元素。缺省情况下，默认使用大顶堆。
c++STL中的优先队列，在此基础上，加以排序，其内部实现是一个二叉堆。即把堆模板化，所有入队的元素拍成具有单调性的一队。

优先队列，元素会被赋予优先级，最先删除的是优先级最高的元素，先进先出的 先出体现在优先级最高的先出去（first in，largest 呕吐）
和queue不同的是，我们可以自定义其中数据的优先级，优先级高的放在前面，先出去

priority——queue特性和操作

本质 堆实现的，具有queue队列的操作和特性

1.头文件&定义

#include<queue>
#include<functional>//greater<>
//定义 priority<Type,Container,Funstional>可缺省后面那个参数，第二个为保存数据的容器，第三个为元素比较的方式
priority_queue<int> pq;//缺省，默认容器vector，比较方式operator<,即大顶堆，队头元素最大
priority_queue<string> q;//string也可以直接比较大小
priority_queue<pair<int,int> >q;//但这个我们自定义的结构体，无法比较，需要重载运算符号


//小顶堆有自己的声明方式，记住即可
priority_queue<int,vector<int>,greater<int> > q;//小顶堆，小的先出对
//注意，<<或者>>放一起的时候，中间要加空格，否则编译器会把两个连在一起判断成位运算的左移和右移

1
2
3
4
5
6
7
8
9
10
11
12

如果自定义元素比较的方式

#include<iostream>
#include<queue>
#include<cstdlib>
using namespace std;
struct Node{
	int x,y;
	Node(int a=0,int b=0):x(a),y(b){}
};
struct myoperator{
	bool operator()(Node a,Node b)
	{
		if(a.x==b.x) return a.y>b.y;
		return a.x>b.x;
	}
};
int main()
{
	priority_queue<Node,vector<Node>,myoperator> p;
	for(int i=0;i<10;i++) p.push(Node(rand(),rand()));
	while(!p.empty()){
		cout<<p.pop().x<<" "<p.top().y<<endl;
		p.pop();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

优先队列的内置函数

添加：
q.push() 插入元素到队尾（并排序）
q.emplace()原地构造一个元素并插入队列
删除：
q.pop()
返回队头：
q.top()
其他都和队列差不多比如q.empty()判空,q.size()队列元素个数，swap交换内容