admin管理员组文章数量:1624317
前言
这几天准备保研机试的时候,再次用到了priority_queue,然而好多内容都忘光了(尤其是结构体的排序),废了很多时间才搞明白一些东西,这里简单的记录下。
一、priority_queue与sort的排序顺序
priority_queue的排序方式跟sort相反。比如sort中的<是升序,而priority_queue中的<是降序,也就是大的优先级高。。。这里我看了一些别人的博客,感觉应该是这样理解 记忆。
priority_queue排的是优先级的顺序,并且是在队尾拿取元素,因此与我们认为的顺序相反。
于是,priority_queue与sort默认用less(<),但sort是升序,priority_queue是大根堆。
二、结构体排序
对于结构体,priority_queue需要重载<(因为priority_queue默认用less),重载方式主要有两种。
1.重载<的成员函数
struct pp{
int first,second;
bool operator <( pp b)const{ //此处的const必须写!!!!,类名前的const可写可不写。
return first<b.first; //这样的重载表示大根堆。
//return first>b.first; //这样表示小根堆。
}
};
priority_queue<pp,vector<pp>,less<pp> > heap;
或者priority_queue<pp> heap; //因为priority默认用less
2.类外重载<
struct pp{
int first,second;
bool friend operator<(pp a,pp b){ //放在类内记得加上友元 ,另外不要加const!!!,因为他不是类的一部分,无法成为常成员函数。
return a.first<b.first; //大根堆
}
};
priority_queue<pp,vector<pp>,less<pp> > heap;
或者priority_queue<pp> heap; //因为priority默认用less
当然我们也可以重载>,但此时priority_queue的定义必须三个参数都写上。
struct pp{
int first,second;
bool operator >( pp b)const{
return first>b.first; //小根堆
//return first<b.first; //大根堆
}
/*bool friend operator>(pp a,pp b){
return a.first>b.first; //小根堆
//return a.first<b.first; //大根堆
}*/
};
priority_queue<pp,vector<pp>,greater<pp> > heap; //此时定义的时候只能这样定义。
另外我们可以发现不管是重载<还是>,都可以独立实现大小根堆,并且我们还可以发现大小根堆只跟return
后面的表达式有关,(左<右为大根堆,左>右为小根堆),因此我们可以为了方便,只重载<,这样在定义的时候就不用写三个参数了。
三、pair与priority_queue
是不是觉得结构体需要重载运算符很麻烦,那么我们可以用模板pair.
typedef pair<int,int>pp;
priority_queue<pp,vector<pp> , greater<pp> > heap; //这样就可以啦,但主要在实现小根堆的时候必须写全三个参数
priority_queue<pp> heap; //这样只能为大根堆。
访问时的方式
pp a;
a.first,a.second;
四、以一段优先队列优化的prime结束吧
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1010,M = 200010,inf = 0x3f3f3f3f;
int head[N],to[M],ne[M],w[M],idx = 0;
struct node{
int a,d;
bool operator> (const node b)const {
return d > b.d;
}
};
int n,m;
int d[N],vt[N];
int ans = -inf;
int prime(){
memset(d,0x3f,sizeof d);
d[1] = 0;
int t = 1;
priority_queue<node,vector<node>,greater<node> > q;
q.push({1,0});
int cnt = 0;
while(!q.empty() && cnt <= n){
node t = q.top();
q.pop();
if(vt[t.a])continue;
cnt++;
vt[t.a] = 1;
ans = max(ans,t.d);
for(int i = head[t.a];~i;i = ne[i]){
int j = to[i];
if(vt[j])continue;
if(w[i] < d[j]){
d[j] = w[i];
q.push({j,w[i]});
}
}
}
if(cnt < n)return -1;
return ans;
}
void add(int a,int b,int c){
w[idx] = c,to[idx] = b,ne[idx] = head[a],head[a] = idx++;
}
int main(){
cin>>n>>m;
memset(head,-1,sizeof head);
for(int i = 0;i < m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
cout<<prime()<<endl;
return 0;
}
版权声明:本文标题:再探c++ priority 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728895064a1178304.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论