c++ priority_queue优先级队列

admin管理员组

文章数量:1623789

优先级队列

当需要获取到最大最小元素值，而又不想用最大最小堆的原生实现，STL提供了更简单的库，就是priority_queue，其时间复杂度也只有 O ( n l o g n ) O(nlogn) O(nlogn)
priority_queue的本质是一个堆，其相对于queue的不同之处在于:优先队列实现了内部自动排序，可根据自己的需要自定义排序规则，可以自己编写函数或者仿函数用于内部优先级的确定。
头文件为#include

1. 模板声明

priority_queue<Type, Container, Functional>

namespace std {
    template < class T ,
           class Container = vector<T> ,
           class Compare = less <typename Container::value_type> >
    class priority_queue ;
}

1. Type:数据类型
2. Container：保存数据的容器（必须是数组实现的容器，比如vector，deque等，不能使用list，默认为vector。）
3. Functional: 元素的比较方式。
   元素的优先级取决于设置的排序函数。如果没有设置，缺省的排序法是利用operator< 形成降序排列，也就是从大到小排列的大顶堆，堆首元素为最大的元素。

1.1 基本函数

1. top()
2. push()
3. pop()

2. 代码实例

2.1. 降序排列

#include <iostream>
#include <queue>
using namespace std;
int main(){
    priority_queue<int> q;
    for( int i= 0; i< 10; ++i ) q.push(i);
    while( !q.empty() ){
        cout<<q.top()<<endl;
        q.pop();
    }
    return 0;
}

2.2. 返回pair的比较结果，先按照pair的first元素降序，first元素相等时，再按照second元素降序

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    priority_queue<pair<int,int> > coll;
    pair<int,int> a(3,4);
    pair<int,int> b(3,5);
    pair<int,int> c(4,3);
    coll.push(c);
    coll.push(b);
    coll.push(a);
    while(!coll.empty())
    {
        cout<<coll.top().first<<"\t"<<coll.top().second<<endl;
        coll.pop();
    }
    return 0;
}

小顶堆：
2.3 如果要用到小顶堆，则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>，基本类型可以用这个仿函数声明小顶堆。

#include <iostream>
#include <queue> 
using namespace std;
int main(){
    priority_queue<int, vector<int>, greater<int> > q;
    for( int i= 0; i< 10; ++i ) q.push(10-i);
    while( !q.empty() ){
        cout << q.top() << endl;
        q.pop();
    }
    return 0;
}

2.4 以下代代码返回pair的比较结果，先按照pair的first元素升序，first元素相等时，再按照second元素升序

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > coll;
    pair<int,int> a(3,4);
    pair<int,int> b(3,5);
    pair<int,int> c(4,3);
    coll.push(c);
    coll.push(b);
    coll.push(a);
    while(!coll.empty())
    {
        cout<<coll.top().first<<"\t"<<coll.top().second<<endl;
        coll.pop();
    }
    return 0;
}

自定义类型
重载operator< 或者重写仿函数
(自定义类型重载operator<后，声明对象时就可以只带一个模板参数)
2.5. 重载operator<:

#include <iostream>
#include <queue> 
using namespace std;
struct Node{
    int x, y;
    Node(int a=0, int b=0):
        x(a),y(b){}
};
bool operator<(Node a, Node b){//返回true时，说明a的优先级低于b
    //x值较大的Node优先级低（x小的Node排在队前）
    //x相等时，y大的优先级低（y小的Node排在队前）
    if( a.x== b.x ) return a.y> b.y;
    return a.x> b.x; 
}
int main(){
    priority_queue<Node> q;
    for( int i= 0; i< 10; ++i )
    q.push( Node( rand(), rand() ) );
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
    return 0;
}

2.6. 小顶堆：此时不能像基本类型这样声明priority_queue<Node,vector,greater >，原因是greater没有定义，如果想用这种方法定义则可以重载operator >。

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}
};
bool operator>( Node a, Node b ){//返回true，a的优先级大于b
    //x大的排在队前部；x相同时，y大的排在队前部
    if( a.x== b.x ) return a.y> b.y;
    return a.x> b.x; 
}
int main(){
    priority_queue<Node,vector<Node>,greater<Node> > q;
    for( int i= 0; i< 10; ++i )
    q.push( Node( rand(), rand() ) );
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
    return 0;
}

2.7. 重写仿函数的例子
小顶堆：

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}
};
struct cmp{
    bool operator() ( Node a, Node b ){//默认是less函数
        //返回true时，a的优先级低于b的优先级（a排在b的后面）
        // x值大的优先级低，x值大的排在队列后面（升序）
        //x相等,y值大的排在队列后面（升序）
        if( a.x== b.x ) return a.y> b.y;      
        return a.x> b.x; }
};
int main(){
    priority_queue<Node, vector<Node>, cmp> q;
    for( int i= 0; i< 10; ++i )
    q.push( Node( rand(), rand() ) );
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
    return 0;
}

参考：https://wwwblogs/Deribs4/p/5657746.html

本文标签： 优先级队列priorityqueue