priority_queue
优先级队列priority_queue
优先级队列是一个拥有权值的gueue，其内部元素按照元素的权值排列。权值较高者排在最前优先出队。其中缺省情况下系统是通过一个max-heap以堆实现完成排序特性，表现为一个以vector表现的完全二叉树。
介绍
它是一个queue，所以只允许在底端加入元素，并从顶端取出元素。
但是优先级队列中的元素并非依照被推入队列的顺序排列。而是自动依照元素的权值排列。权值最高者排在最前面。
缺省的情况下维护的是一个大堆，即权值以从高到低排列。
参数
priority_queue<Type, Container, Functional>
其中Type代表数据类型
Container代表容器类型，缺省状态为vector
Functional是比较方式，默认采用的是大顶堆(less<>)。
//升序队列 小顶堆 great小到大
priority_queue <int,vector<int>,greater<int>> minheap;
//降序队列 大顶堆 Less大到小 默认
priority_queue<int,vector<int>,less<int>> maxheap;
priority_queue<int> maxheap;
api
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q·push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top()：//返回q的第一个元素
使用技巧
使用优先队列时往往不局限于int 对于复杂的数据结构 该怎么让他保持大小根的特性呢
重载<
它也是默认用 operator< 表示大根堆的 要改成小根堆或者设置什么多关键字排序也是一样的原理 要么把<重载成>或自己想要的比较规则
#include<bits/stdc++.h>
using namespace std;
struct node1{
int x,y;
bool operator<(const node1& other)const{
return x<other.x;
}
};
priority_queue<node1> maxheap;
struct node2{
int x,y;
bool operator<(const node2& other)const{
return x>other.x;
}
};
priority_queue<node2> minheap;
int main()
{
node1 a1={1,2};node1 b1={0,2};node1 c1={1,3};node1 d1={2,5};
maxheap.push(a1);maxheap.push(b1);maxheap.push(c1);maxheap.push(d1);
while(!maxheap.empty()){
cout<<maxheap.top().x<<","<<maxheap.top().y<<endl;
maxheap.pop();
}
cout<<endl;
node2 a2={1,2};node2 b2={0,2};node2 c2={1,3};node2 d2={2,5};
minheap.push(a2);minheap.push(b2);minheap.push(c2);minheap.push(d2);
while(!minheap.empty()){
cout<<minheap.top().x<<","<<minheap.top().y<<endl;
minheap.pop();
}
return 0;
}
仿函数
要么就直接重写一个比较规则 传入参数里告诉它让它使用
#include<bits/stdc++.h>
using namespace std;
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
};
struct CompareAge_max {
bool operator()(const Person& a, const Person& b) {
return a.age < b.age; // 较大的年龄优先
}
};
struct CompareAge_min {
bool operator()(const Person& a, const Person& b) {
return a.age > b.age; // 较大的年龄优先
}
};
priority_queue<Person, vector<Person>, CompareAge_max> people_maxheap;
priority_queue<Person, vector<Person>, CompareAge_min> people_minheap;
int main()
{
Person a={"张三",17}; Person b={"李四",19}; Person c={"王五",12};
people_maxheap.push(a);people_maxheap.push(b);people_maxheap.push(c);
while(!people_maxheap.empty()){
cout<<people_maxheap.top().name<<","<<people_maxheap.top().age<<endl;
people_maxheap.pop();
}
puts(" ");
people_minheap.push(a);people_minheap.push(b);people_minheap.push(c);
while(!people_minheap.empty()){
cout<<people_minheap.top().name<<","<<people_minheap.top().age<<endl;
people_minheap.pop();
}
return 0;
}
或者这样
#include<bits/stdc++.h>
using namespace std;
template <typename T>
class cmp_max{
public:
bool operator()(T a,T b)
{
return a.age<b.age;
}
};
template <typename T>
class cmp_min{
public:
bool operator()(T a,T b)
{
return a.age>b.age;
}
};
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
};
priority_queue<Person, vector<Person>, cmp_max<Person>> people_maxheap;
priority_queue<Person, vector<Person>, cmp_min<Person>> people_minheap;
int main()
{
Person a={"张三",17}; Person b={"李四",19}; Person c={"王五",12};
people_maxheap.push(a);people_maxheap.push(b);people_maxheap.push(c);
while(!people_maxheap.empty()){
cout<<people_maxheap.top().name<<","<<people_maxheap.top().age<<endl;
people_maxheap.pop();
}
puts(" ");
people_minheap.push(a);people_minheap.push(b);people_minheap.push(c);
while(!people_minheap.empty()){
cout<<people_minheap.top().name<<","<<people_minheap.top().age<<endl;
people_minheap.pop();
}
return 0;
}
此外还有lambda表达式和函数指针的写法
越往下越不推荐 还是在node里面重载<最方便 灵活性高的话就直接写个仿函数（其一）
小结
反正可以观察到一个东西 就是<对应的就是大根堆 >对应的是小根堆
这与sort居然是相反的（sort <升序 >降序）
理解成对头在右侧就没问题了
优先级队列排序函数的顺序问题
对于sort和priority_queue，使用greater和less类模板是结果不同的。
主要原因是因为priority_queue的内部实现方法是堆，less对应的是大顶堆。在此排序下调用top()得到的是堆顶，也就是取值时是从大到小。push对应的底层函数是push*heap()，每次添加元素入堆时，在默认情况下添加进去的数据作为较小值入堆。
//默认都是Less
sort(vec.begin(),vec.end(),less<int>());//内置类型从小到大升序
priority_queue <int,vector<int>,less<int> > pql;//top出数据从大到小降序
sort(vec.begin(),vec.end(),greater<int>());//内置类型从大到小降序
priority_queue<int,vector<int>,greater<int>>pqg;//top出数据从小到大升序
除了priority_queue使用的是堆，导致全部大小比较反了过来，其他均是正常符合逻辑的操作，即判断为func(a,b)判断为true则a在前。
只有priority_queue特殊，如果func(a,b)判断为true，优先级队列中b在前
注意：队头在最右侧
struct node{
int x,y;
}point;
bool operator<(const node &a,const node &b)
{
if(a.x==b.x)
return a.y>b.y;
else
return a.x<b.x;
}
priority_queue<node> Q;
1、Sort排序里面的比较函数，将元素按照比较函数的逻辑排序
2、优先队列priority_queue里面默认使用大顶堆，也就是less<>，并不是按照比较的顺序直接进行排序。
3、如上述代码，对于a和b的排序，先对a.x和b.x进行比较，如果前者小，其优先级低，放在后面，按照降序排列；如果两者相等，再对a.y和b.y进行比较，如果前者小，此时优先级高，放在前面，按照升序排列。
4、总结，先按照x降序排列，对于x相同的，按照y升序排列，而非直接根据大小进行排列。排列的标准是优先级，而非具体的数值大小。返回true代表优先级更低。
💬 评论