优先队列(priority_queue)，实际上，它的本质就是一个heap，可以参考传送门
这个写的也不错
优先级队列是一个拥有权值观念的queue。它允许在底端添加元素、在顶端去除元素、删除元素。 缺省情况下，优先级队列利用一个大顶堆完成。
而C++STL中的优先队列就是在这个队列的基础上，把其中的元素加以排序。其内部实现是一个二叉堆。所以优先队列其实就是把堆模板化，将所有入队的元素排成具有单调性的一队，方便我们调用。
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest
out）的行为特征。
首先要包含头文件#include, 他和queue不同的就在于我们可以自定义其中数据的优先级,让优先级高的排在队列前面,优先出队。
优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。
#include <queue>
#include <functional> //greater<>
// 定义
priority_queue<int> pq;
priority_queue<Type, Container, Functional>
其中, Type 为数据类型. Container 为保存数据的容器. Functional 为元素比较的方式.
若不写后面两个参数.
容器 默认使用 vector
比较方式 默认使用 operator < 即优先队列是大顶堆. 队头元素最大
大根堆声明方式：
大根堆就是把大的元素放在堆顶的堆。优先队列默认实现的就是大根堆，所以大根堆的声明不需要任何花花肠子，直接按C++STL的声明规则声明即可。
#include<queue>
priority_queue<int> q;
priority_queue<string> q;
priority_queue<pair<int,int> > q;
C++中的int,string等类型可以直接比较大小，所以不用我们多操心，优先队列自然会帮我们实现。但是如果是我们自己定义的结构体，就需要进行重载运算符了
srand(time(NULL));
priority_queue<int> pq1; // 默认是最大堆...
std::cout << "start..." << endl;
for (int i = 0; i < 10; i++) {
int t = rand() % 100;
cout << t << ends;
pq1.push(t);
}
std::cout << endl;
while (!pq1.empty())
{
cout << pq1.top() << ends;
pq1.pop();
}
cout << endl;
输出：
priority_queue<int, vector<int>, greater<int> > p;greater<int> . 即改用 operator >实现小根堆有两种方式：
第一种是比较巧妙的，因为优先队列默认实现的是大根堆，所以我们可以把元素取反放进去，因为负数的绝对值越小越大，那么绝对值较小的元素就会被放在前面，我们在取出的时候再取个反，就瞒天过海地用大根堆实现了小根堆。
第二种：
小根堆有自己的声明方式，我们记住即可（我也说不明白道理）：
priority_queue<int,vector<int>,greater<int> >q;
注意，当我们声明的时候碰到两个"<“或者”>"放在一起的时候，一定要记得在中间加一个空格。这样编译器才不会把两个连在一起的符号判断成位运算的左移/右移。
priority_queue<int, vector<int>, greater<int>> pq2; // 最小堆
std::cout << "start..." << endl;
for (int i = 0; i < 10; i++) {
int t = rand() % 100;
std::cout << t << ends;
pq2.push(t);
}
std::cout << endl;
while (!pq2.empty())
{
cout << pq2.top() << ends;
pq2.pop();
}
cout << endl;
结果：
// 定义比较函数
// 后面一个表示栈顶元素? 所以这个是 "最小堆"
bool myCom(int a, int b) {
return a % 10 > b % 10;
}
// 使用
priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCom);
std::cout << "start..." << endl;
for (int i = 0; i < 10; i++) {
int t = rand() % 100;
std::cout << t << ends;
pq3.push(t);
}
std::cout << endl;
while (!pq3.empty())
{
cout << pq3.top() << ends;
pq3.pop();
}
cout << endl;
输出结果：
#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 cmp{
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>, cmp>p;
for(int i=0; i<10; ++i)
p.push(Node(rand(), rand()));
while(!p.empty()){
cout<<p.top().x<<' '<<p.top().y<<endl;
p.pop();
}//while
//getchar();
return 0;
首先函数在头文件中，归属于命名空间std，使用的时候需要注意。
priority_queue<int> q1;
priority_queue< pair<int, int> > q2; // 注意在两个尖括号之间 一定要留空格。
priority_queue<int, vector<int>, greater<int> > q3; // 定义小的先出队
1.普通方法
priority_queue<int> q;
//通过操作，按照元素从大到小的顺序出队
priority_queue<int,vector<int>, greater<int> > q;
//通过操作，按照元素从小到大的顺序出队
2、自定义优先级：
struct cmp {
operator bool ()(int x, int y)
{
return x > y; // x小的优先级高
//也可以写成其他方式，
//如： return p[x] > p[y];表示p[i]小的优先级高
}
};
priority_queue<int, vector, cmp> q; //定义方法
//其中，第二个参数为容器类型。第三个参数为比较函数。
3、结构体声明方式：
struct node {
int x, y;
friend bool operator < (node a, node b)
{
return a.x > b.x; //结构体中，x小的优先级高
}
};
priority_queue<node>q; //定义方法
//在该结构中，y为值, x为优先级。
//通过自定义operator<操作符来比较元素中的优先级。
//在重载”<”时，最好不要重载”>”，可能会发生编译错误
q.push();插入元素到队尾 (并排序)q.emplace(); 原地构造一个元素并插入队列q.pop();弹出队头元素q.empty();队列是否为空q.size() 返回队列内元素个数q.top() ;访问队头元素,返回队列首元素，不改变队列swap 交换内容top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容
| 用法 | 作用 |
|---|---|
| q.top() | 返回priority_queue的首元素 |
| q.push() | 向priority_queue中加入一个元素 |
| q.size() | 返回priority_queue当前的长度（大小） |
| q.pop() | 从priority_queue队头删除一个元素 |
| q.empty() | 返回priority_queue是否为空，1为空、0不为空 |
注意：priority_queue取出队首元素是使用top，而不是front，这点一定要注意！！
#include<iostream>
#include <queue>
using namespace std;
int main()
{
//对于基础类型 默认是大顶堆
priority_queue<int> a;
//等同于 priority_queue<int, vector<int>, less<int> > a;
// 这里一定要有空格，不然成了右移运算符↓↓
priority_queue<int, vector<int>, greater<int> > c; //这样就是小顶堆
priority_queue<string> b;
for (int i = 0; i < 5; i++)
{
a.push(i);
c.push(i);
}
while (!a.empty())
{
cout << a.top() << ' ';
a.pop();
}
cout << endl;
while (!c.empty())
{
cout << c.top() << ' ';
c.pop();
}
cout << endl;
b.push("abc");
b.push("abcd");
b.push("cbd");
while (!b.empty())
{
cout << b.top() << ' ';
b.pop();
}
cout << endl;
return 0;
}
运行结果：
4 3 2 1 0
0 1 2 3 4
cbd abcd abc
请按任意键继续. . .
规则：pair的比较，先比较第一个元素，第一个相等比较第二个。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty())
{
cout << a.top().first << ' ' << a.top().second << '\n';
a.pop();
}
}
运行结果：
2 5
1 3
1 2
请按任意键继续. . .
#include <iostream>
#include <queue>
using namespace std;
//方法1
struct tmp1 //运算符重载<
{
int x;
tmp1(int a) {x = a;}
bool operator<(const tmp1& a) const
{
return x < a.x; //大顶堆
}
};
//方法2
struct tmp2 //重写仿函数
{
bool operator() (tmp1 a, tmp1 b)
{
return a.x < b.x; //大顶堆
}
};
int main()
{
tmp1 a(1);
tmp1 b(2);
tmp1 c(3);
priority_queue<tmp1> d;
d.push(b);
d.push(c);
d.push(a);
while (!d.empty())
{
cout << d.top().x << '\n';
d.pop();
}
cout << endl;
priority_queue<tmp1, vector<tmp1>, tmp2> f;
f.push(b);
f.push(c);
f.push(a);
while (!f.empty())
{
cout << f.top().x << '\n';
f.pop();
}
}
运行结果：
3
2
1
3
2
1
请按任意键继续. . .