说明：
- 文章内容为关于
priority_queue的使用总结，在C++中要包含头文件<queue> - 文章内容为个人的学习整理，如有错误，欢迎指正。
文章目录
- 1. 优先队列默认是大根堆
- 2. 关于优先队列和sort的比较逻辑
- 2.1 sort的比较逻辑
- 2.2 优先队列的比较逻辑
- 2.2.1 优先队列的验证
- 2.2.2 sort的验证
- 2.3 优先队列和sort比较逻辑的区别简记
- 3. 自定义比较逻辑
1. 优先队列默认是大根堆
优先队列默认使用大根堆结构，例如：
int main()
{
vector<int> v = {0,1,2,3,4,5,6,7,8,9};
priority_queue<int> pq;
for(int i=0; i<v.size(); i++)
pq.push(v[i]);
while(!pq.empty())
{
cout<<pq.top()<<" ";
pq.pop();
}
return 0;
}
输出结果为：
9 8 7 6 5 4 3 2 1 0
默认的输出序列是一个降序序列。
2. 关于优先队列和sort的比较逻辑
2.1 sort的比较逻辑
而sort的默认输出结果是升序的。sort的默认比较逻辑是less<>，因此对于vector<int> v = {0,1,2,3,4,5,6,7,8,9};有以下结果：
sort(v.begin(), v.end()); //输出为0 1 2 3 4 5 6 7 8 9
sort(v.begin(), v.end(),less<>()); //0 1 2 3 4 5 6 7 8 9
sort(v.begin(), v.end(),greater<>());//9 8 7 6 5 4 3 2 1 0
2.2 优先队列的比较逻辑
优先队列和sort比较逻辑的区别（这也是我之前理解的一个误区），还是对上面的数组，由优先队列输出的结果为：
priority_queue<int, vector<int>> pq;//9 8 7 6 5 4 3 2 1 0
priority_queue<int, vector<int>, less<int>> pq;//9 8 7 6 5 4 3 2 1 0
priority_queue<int, vector<int>, greater<int>> pq;//0 1 2 3 4 5 6 7 8 9
优先队列默认输出是大根堆的输出，即结果是升序的，但它的默认比较逻辑是less<>。
这里我一直想不明白为什么相同的比较逻辑却得到不同的输出结果，多方查阅资料后，有解释说是因为传参的顺序不同。例如cmp<int a, int b>，a，b作为比较逻辑中的两个参数，新参与比较的元素是作为第一个参数还是第二个元素，这个差异导致了sort和priority_queue输出了不同的结果。下面来简单验证一下：
2.2.1 优先队列的验证
结论：优先队列将未进入队列的元素作为cmp的第二个参数传入。
验证如下：
- 定义比较逻辑
//priority_queue比较逻辑
struct cmp_2
{
bool operator() (int a, int b)
{
cout<<"priority_q cmp: "<<a<<" "<<b<<endl;
return a < b;
}
};
- 定义优先队列并输入数据，观察元素在入队过程中的比较过程
priority_queue<int, vector<int>, cmp_2> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5);
将1~5依次入队，这个过程中的输出为：
priority_q cmp: 1 2
priority_q cmp: 2 3
priority_q cmp: 1 4
priority_q cmp: 3 4
priority_q cmp: 3 5
priority_q cmp: 4 5
比较过程的简图如下：
可见每次新入队的元素都作为cmp的第二个参数参与比较。优先队列是用大根堆实现的，因此图中的cmp过程也就是大根堆的调整过程。
之后依次弹出堆顶也就是出队的过程，就得到了一个降序序列（大根堆，堆顶元素最大）
2.2.2 sort的验证
结论：sort将未排好的元素作为cmp的第一个参数传入。
验证如下：
- 定义比较逻辑
bool cmp_1 (int a, int b)
{
cout<<"sort cmp: "<<a<<" "<<b<<endl;
return a < b;
}
- 创建数组输入元素，执行sort函数，观察元素在排序过程中的比较情况
vector<int> nums;
nums.push_back(5);
nums.push_back(4);
nums.push_back(3);
nums.push_back(2);
nums.push_back(1);
sort(nums.begin(), nums.end(), cmp_1);
将5~1一次存入数组，之后执行sort函数，这个过程的输出为：
sort cmp: 4 5
sort cmp: 3 4
sort cmp: 2 3
sort cmp: 1 2
比较过程的简图如下：（说明：sort的底层是内省式排序和插入排序，所以下图中的比较过程并不完整，仅仅是为了显示参与比较的元素是作为第几个参数传入的）
可见每次未排好的元素作为cmp的第一个参数传入，
2.3 优先队列和sort比较逻辑的区别简记
说明：下面的方法是我个人为了方便理解而整理的方法，可能有不严谨的地方，各位酌情观看。
| 输出序列的优先级：高--->低 | ||
| sort | less : 1,2,3,4,5 | 值越小，优先级越高 |
| greater：5,4,3,2,1 | 值越大，优先级越高 | |
| priority_queue | less：5,4,3,2,1 | 值越大，优先级越高 |
| greater：1,2,3,4,5 | 值越小，优先级越高 |
记忆的话，sort就正着记：
- less就是升序，排在前面的比后面小，前less后
- greater就是降序，排在前面的比后面的大，前greater后
优先队列就反着记：（其实和优先队列是大根堆有关）
- less就是降序，排在前面的比后面大，后less前
- greater就是升序，排在前面的比后面小，后greater前
3. 自定义比较逻辑
最后做个小实验，自定义比较逻辑，验证结果的正确性。
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}A;
//定义sort的比较逻辑
bool cmp_1 (node a, node b)
{
if(a.x != b.x) return a.x < b.x;
else return a.y > b.y;
}
//定义priority_queue的比较逻辑
struct cmp_2
{
bool operator() (node a, node b)
{
if(a.x != b.x) return a.x < b.x;
else return a.y > b.y;
}
};
int main()
{
priority_queue<node, vector<node>, cmp_2> pq;
vector<node> v;
A.x = 1, A.y = 9, pq.push(A), v.push_back(A);
A.x = 1, A.y = 8, pq.push(A), v.push_back(A);
A.x = 2, A.y = 9, pq.push(A), v.push_back(A);
A.x = 3, A.y = 9, pq.push(A), v.push_back(A);
A.x = 4, A.y = 6, pq.push(A), v.push_back(A);
sort(v.begin(), v.end(), cmp_1);
cout<<"sort cmp result"<<endl;
for(int i=0; i<v.size(); i++)
cout<<v[i].x<<" "<<v[i].y<<endl;
cout<<"priority_queue cmp result"<<endl;
while(!pq.empty())
{
cout<<pq.top().x<<" "<<pq.top().y<<endl;
pq.pop();
}
return 0;
}
输出结果为：
sort cmp result
1 9
1 8
2 9
3 9
4 6
priority_queue cmp result
4 6
3 9
2 9
1 8
1 9
其实关于sort和优先队列的自定义比较逻辑都是
if(a.x != b.x) return a.x < b.x;
else return a.y > b.y;
可以看到输出结果恰好相反，就对应了sort的less和greater逻辑和优先队列的less和greater逻辑是相反的。
