前言：建议初学者跟着把每一个样例打一遍，并自己改变代码做到更多不同的效果。
优先队列是什么，干嘛用的
优先队列，即带有优先级的队列。不懂啥是队列的可以先去学队列了（先进先出的就是队列）。那么带有优先级，就是可以做到排序的队列，比如我依次放入2，1，3，小顶堆优先队列就可以通过1，2，3的顺序把他们吐出来。而一般的队列只能以2，1，3的顺序把他们吐出来。
作用：
以最短路和BFS为例，就经常使用优先队列。当然其他问题和算法也经常使用优先队列。
要学些什么
学习优先队列的基础用法前，你可以啥也没学，只会用法就行。但是要想知道优先队列的原理，实现优先队列的自定义，建议至少把二叉树，堆排序给学了，最好把C++的类也学了。这里不会讲优先队列的原理，而是注重使用方法。这东西学会怎么用比学会原理的时间要早太多了。
如果代码看着眼花，那就跟着打一次，边打边尝试理解它的意思。
一定要上手实践
优先队列的定义：
priority_queue<Type, Container, Functional>
Type
是数据类型；
Container
是容器类型，一般使用vector；
Functional
是比较的方式。
优先队列的基本操作：
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾并排序
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容
基础使用
学会使用这部分前你不需要懂它到底啥原理。
注：
大顶堆：字面意思，根（顶）最大的堆。
小顶堆：根（顶）最小的堆。
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
//_________________默认为大顶堆_________________
priority_queue<int> q1;
//_________________标准一般写法_________________
//小顶堆
priority_queue<int,vector<int>,greater<int> > q2;
//大顶堆
priority_queue<int,vector<int>,less<int> >q3;
priority_queue<string,vector<string>, greater<string> >q4;
int main()
{
//测试样例1,默认情况
q1.push(2);
q1.push(1);
q1.push(4);
cout<<"q1:";
while(!q1.empty()){
cout<<q1.top()<<" ";
q1.pop();
}
cout<<endl;
//测试样例2，小顶堆
q2.push(3);
q2.push(2);
q2.push(1);
cout<<"q2:";
while(!q2.empty()){
cout<<q2.top()<<" ";
q2.pop();
}
cout<<endl;
//测试样例3：大顶堆
q3.push(1);
q3.push(2);
q3.push(3);
cout<<"q3:";
while(!q3.empty()){
cout<<q3.top()<<" ";
q3.pop();
}
cout<<endl;
//测试样例4：字符串形式
q4.push("hello");
q4.push("issey");
q4.push("abc");
q4.push("cccf");
cout<<"q4:";
while(!q4.empty()){
cout<<q4.top()<<" ";
q4.pop();
}
cout<<endl;
return 0;
}
进阶使用
在学习这部分前，你可以不学前置知识，但顶多只能照猫画虎，建议现学上面提到的前置知识，再来学就很好懂了。
进阶1：pair
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
//_____________piar_________________
//标准写法
priority_queue<pair<int,string>,vector<pair<int,string> >,greater<pair<int,string> > >q1;
//当然也可以简写，不过默认大顶堆
priority_queue<pair<int,int> >q2;
int main()
{
//测试样例1:
pair<int,string> a(1,"issey");
pair<int,string> b(1,"aaa");
pair<int,string> c(2,"zz");
q1.push(a);
q1.push(b);
q1.push(c);
cout<<"q1:"<<endl;
while(!q1.empty()){
cout<<q1.top().first<<" ";
cout<<q1.top().second<<endl;
q1.pop();
}
//测试样例2:
pair<int,int> A(1,1);
pair<int,int> B(1,2);
pair<int,int> C(2,0);
q2.push(A);
q2.push(B);
q2.push(C);
cout<<"q2:"<<endl;
while(!q2.empty()){
cout<<q2.top().first<<" ";
cout<<q2.top().second<<endl;
q2.pop();
}
return 0;
}
进阶2：自定义优先队列
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
//__________方法1：在结构体里重载运算符________
typedef struct Node{
int sum,id;
friend bool operator<(Node a,Node b){
return a.sum>b.sum;//通过属性sum建立小顶堆
}
}Node;
priority_queue<Node> q1;
/*
关于结构体重载运算符和优先队列定义的解释：
priority_queue<Node> q1是默认定义方式，我们知道默认的应该是大顶堆，堆排序构建大顶
堆时，应该是当前节点小于（左、右）孩子，才进行交换，所以默认的运算符是'<'，所以在结构体
重载运算符时，应该是friend bool operator<(Node a,Node b)。
而我们想实现通过sum建立小顶堆，所以重载'<'时，把真正的比较对象置为'>','>'是构建小顶
堆，所以使用默认方式建立优先队列，本来要读'<',实际上读的是'>',就简化了书写。（笑，这种方
法太坏蛋了）
*/
//_________________方法2：重写仿函数__________________
typedef struct Node2{
int id,sum;
}Node2;
struct cmp{
bool operator()(const Node2 a,const Node2 b){
return a.sum<b.sum;//通过sum构建大顶堆
}
};
priority_queue<Node2,vector<Node2>,cmp >q2;
int main()
{
//测试样例1
Node a,b,c;
a.id = 1;a.sum = 10;
b.id = 2;b.sum = 3;
c.id = 3;c.sum = 6;
q1.push(a);
q1.push(b);
q1.push(c);
cout<<"q1:"<<endl;
while(!q1.empty()){
Node temp = q1.top();
q1.pop();
cout<<"id:"<<temp.id<<" "<<"sum:"<<temp.sum<<endl;
}
//测试样例2：
Node2 A,B,C;
A.id = 1;A.sum = 3;
B.id = 2;B.sum = 20;
C.id = 3;C.sum = 1;
q2.push(A);
q2.push(B);
q2.push(C);
cout<<"q2:"<<endl;
while(!q2.empty()){
Node2 temp = q2.top();
q2.pop();
cout<<"id:"<<temp.id<<" "<<"sum"<<temp.sum<<endl;
}
return 0;
}