C语⾔优先队列（priorityqueue）详解
0x00，优先队列（priority queue）
priority queue是⼀个⽤"堆"实现的，类似set的容器，有着queue的基本功能。特征是"具有优先级，可以按照优先级出队"
可能不是特别好理解，其实就是⼀个排序啦。。。
举个栗⼦：
3⼊队，4⼊队，1⼊队，如果是queue的容器，出队顺序为3,4,1，⽽priority queue则在内部会排好序，出队顺序为4,3,1。
这种数据结构在解决⼀些⾼级问题，例如贪⼼类问题，或者迪杰斯特拉算法，都可以更加⽅便的解决问题。
c语言struct头文件0x01，声明与操作
声明与操作和queue基本⼀样，例如这段程序：
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<int> q;
q.push(3);
q.push(4);
q.push(2);
cout << q.top();
return 0;
}
输出的结果是 4 。
如果加上出队程序，出队的序列为4,3,2 。
queue中的pop，size，empty等函数在priority_queue中仍然适⽤。
0x02，基本数据类型优先级的设置
在前⾯，priority queue默认的顺序总是数字⼤的优先级⾼，⽽如果我们需要⾃定义优先级呢
解决这⼀问题很简单，我们只需要改变⼀下定义priority queue的⽅式即可：
priority_queue<ElementType, vector<ElementType>, less<int> > q;
这样，数字⼤的优先级⼤
在这⾥，三个ElementType的类型必须保持⼀致。这⾥vector是队列内部⽤于承载底层数据结构堆的容器，less是对第⼀个参数的⽐较类。
less表⽰数字越⼤优先级越⼤（如果是char类型则根据ASCII码来判断），如果希望数字越⼩优先级越⼤，只需要将less换成greater即可。例如
priority_queue<ElementType, vector<ElementType>, less<int> > q;
要注意最后⼀个‘>’与下⼀个‘>’之间必须有空格。否则编译器会误认为是在做移位运算。
这⾥很容易记混，再次重复⼀遍：
less -> 数字⼤的优先级⼤，数字⼤被放在队⾸。所以先输出数字⼤的
greater -> 数字⼩的优先级⼤，数字⼩被放在队⾸。所以先输出数字⼩的
继续举栗⼦：
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<int, vector<int>, less<int> > q;
q.push(8);
q.push(3);
q.push(5);
while(!q.empty()){
cout << q.top() << endl;
q.pop();
}
return 0;
}
运⾏结果：
0x03，结构体的优先级设置
⽐如博主是个卖⽔果的，我希望写个程序，帮助我优先卖出贵的⽔果。
⾸先我定义⼀个结构体变量：
struct fruit{
string name;    //⽔果名
int price;      //⽔果价格
};
如果我们直接把结构体压⼊priority queue，代码：
struct fruit{
string name;
int price;
}f1,f2,f3;
int main(){
priority_queue<fruit> q;
/*定义⽔果和价格*/
f1.name = "桃⼦"; f1.price = 3;
f2.name = "梨"; f2.price = 4;
f3.name = "苹果"; f3.price = 1;
/*压⼊队列*/
q.push(f1);q.push(f2);q.push(f3);
while(!q.empty()){
cout << q.top().name << '\t' << q.top().price << endl;
q.pop();
}
return 0;
}
得到的结果是这样的：
好吧，编译都通不过，⼤概的意思是，C++中，queue的操作库直接使⽤了⼩于号⽐较⼤⼩，⽽结构体之间不能使⽤⼩于号⽐较，所
以，boom。
这⾥我们可以重载⼩于号，也就是重新让编译器理解⼩于号的意思。
（⽐如编译器默认的⼩于号意思是直接⽐较⼩于号两边数字的⼤⼩，我们可以重新定义⼩于号，让编译器认为⼩于号是⽐较结构体中某些变量的⼤⼩。如果还是没有太理解，可以想想algorithm头⽂件中sort函数。这⾥重新定义⼩于号，也就相当于定义sort函数中的cmp函数）
（这⾥必须重载⼩于号，不能重载⼤于号，因为从上图中可以看出，C++queue的库函数采⽤的是⼩于号，所以定义⼤于号是没⽤滴）
我们修改结构体的定义⽅式，使得重载⼩于号：
struct fruit{
string name;
int price;
friend bool operator < (fruit f1, fruit f2){//重新定义bool类型操作符‘<’，
//‘<’的两边分别是fruit类型的f1和f2
return f1.price < f2.price;//操作符返回f1.price是否⼩鱼f2.price
}
}
这⾥friend的意思是"友元"。当然，你也可以把return后⾯的‘<’改为‘>’，这样就可以反着排序了。
struct fruit{
string name;
int price;
friend bool operator < (fruit f1, fruit f2){
return f1.price < f2.price;
}
}f1,f2,f3;
int main(){
priority_queue<fruit> q;
/*定义⽔果和价格*/
f1.name = "桃⼦"; f1.price = 3;
f2.name = "梨"; f2.price = 4;
f3.name = "苹果"; f3.price = 1;
/*压⼊队列*/
q.push(f1);q.push(f2);q.push(f3);
while(!q.empty()){
cout << q.top().name << '\t' << q.top().price << endl;      q.pop();
}
return 0;
}
结果：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。