C++优先队列priority_queue的使用和应用(dijkstra堆优化)

admin管理员组

文章数量:1624351

C++中使用优先队列需要包含头文件#include< queue >。
常用的方法:
1.push(type);
2.pop();
3.top();
4.empty();

声明格式为:
priority_queue<type,容器,优先级比较方式(为类或结构体)>：
/* 没看过STL实现priority_queue的源码，不确定这个格式准不准确 */

举例：

priority_queue<int,vector< int >,greater< int > >    //小根堆
priority_queue<int,vector< int >,less< int > >    //大根堆

对于基本类型，，也可以

priority_queue< int >       //默认为vector,less< int >，即大根堆

对于自定义类型，需要自己定义比较函数或者重载运算符 ’ < ’

比如说：

struct node{
	int a , b;
	bool operator < (const node &x) const {  //此处为优先级的比较   
	                                          //大根堆
		if(a == x.a)return b < x.b;
		else return a < x.a;
	}
	//也可用友元
};

或者自定义  cmp:

class cmp{
	public:
	bool operator() ( node x, node y){     //y的优先级大
		if(x.a == y.a)return x.b > y.b;    //小根堆
		else return x.a > y.a;
	}
};

声明时 :
priority_queue< node >;
或者 priority_queue< node ,vector< node >, cmp>;

下面以dijkstra的堆优化来具体讲解priority_queue的应用:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 2510,inf = 0x3f3f3f3f,C = 6210;

typedef pair<int,int>pp;

class cmp{
    public:
        bool operator() (pp a,pp b){
            return b.second <= a.second;
        }
};

struct node{
    int to,w,next;
}edge[2*C];

int head[N],v[N],d[N];
int cnt = 0;
int n,m;

void add(int a,int b,int c){
    edge[cnt].to = b;
    edge[cnt].w = c;
    edge[cnt].next = head[a];
    head[a] = cnt++;
}

void dijkstra(int sv){
    memset(d,0x3f,sizeof d);
    d[sv] = 0;
    int a = sv;
    priority_queue< pp,vector<pp>,cmp > q;
    q.push({a,d[a]});
    while(!q.empty()){
        auto h = q.top();
        q.pop();
        if(v[h.first])continue;   /*某一个结点可能被不同点更新，
                                  会多次入队，故需要排重。*/
        v[h.first] = 1;
        for(int i = head[h.first];~i;i = edge[i].next){
            int b = edge[i].w,c = edge[i].to;
            if(h.second + b < d[c]){
                d[c] = h.second+b;
                q.push({c,d[c]});
            }
        }
    }
    
}
int main(){
    int sv,ev;
    cin>>n>>m>>sv>>ev;
    for(int i = 0;i < N;i++){
        head[i] = -1;
        edge[i].next = -1;
    }
    for(int i = 0;i < m;i++){
        int from,to,w;
        cin>>from>>to>>w;
        add(from,to,w);
        add(to,from,w);
    }
    dijkstra(sv);
    cout<<d[ev]<<endl;
    return 0;
}

本文标签： 队列priorityqueueDijkstra