再探c++ priority

admin管理员组

文章数量:1624324

前言

这几天准备保研机试的时候，再次用到了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;
}

本文标签： 再探Priority