C/C++编程：优先队列priority_queue

叁歲伎倆 2023-02-27 03:24 152阅读 0赞

> priority\_queue本质是一个堆。

1 . 头文件是\#include

2 . 关于priority\_queue中元素的比较

模板申明带3个参数：priority\_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素比较方式。

Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector。

2.1 比较方式默认用operator<，所以如果把后面2个参数缺省的话，优先队列就是大顶堆（降序），队头元素最大。特别注意pair的比较函数。

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

#include <functional>
    #include <queue>
    #include <vector>
    #include <iostream>
    
    template<typename T> void print_queue(T& q) {
        
        while(!q.empty()) {
        
            std::cout << q.top() << " ";
            q.pop();
        }
        std::cout << '\n';
    }

int main() {
        
        //-----------------------------如果想要降序-------------------------------------
        std::priority_queue<int >q;  // 等同于 std::priority_queue<int,std::vector<int> , std::less<int> >q;
        for(int n : {
        1,8,5,6,3,4,0,9,7,2})
            q.push(n);
        print_queue(q);
    
        // ---------------------------如果想要升序------------------------------
        std::priority_queue<int,std::vector<int> , std::greater<int> >q2;
        for(int n : {
        1,8,5,6,3,4,0,9,7,2})
            q2.push(n);
    
        print_queue(q2);
    
    
        //------------------------自定义lambar比较------------------------------
    // Using lambda to compare elements.
        auto cmp = [](int left, int right) {
         return (left ^ 1) < (right ^ 1); };
        std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
    
        for(int n : {
        1,8,5,6,3,4,0,9,7,2})
            q3.push(n);
    
        print_queue(q3);
    
    }

![在这里插入图片描述][20200716110340947.png]

以下代代码返回pair的比较结果，

#include <functional>
    #include <queue>
    #include <vector>
    #include <iostream>
    
    template<typename T> void print_queue(T& q) {
        
        while(!q.empty()) {
        
            std::cout <<q.top().first<<" "<<q.top().second << " \t\t";
            q.pop();
        }
        std::cout << '\n';
    }
    
    int main() {
        
       // 默认先按照pair的first元素降序，first元素相等时，再按照second元素降序：
        std::priority_queue<std::pair<int, int>>q;
        // 下面是：先按照pair的first元素升序，first元素相等时，再按照second元素升序： 
        // std::priority_queue<pair<int,int>, std::vector<pair<int,int> >, std::greater<pair<int,int> > > q;
        std::pair<int,int> a(3,4);
        std::pair<int,int> b(3,5);
        std::pair<int,int> c(4,3);
        q.push(a);
        q.push(b);
        q.push(c);
        print_queue(q);
    }

![在这里插入图片描述][20200716110722390.png]  
2.2、对于自定义类型，则必须重载operator<或者重写仿函数。

*  重载operator<的例子：返回true时，说明左边形参的优先级低于右边形参

#include <functional>
    #include <queue>
    #include <vector>
    #include <iostream>
    
    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() {
        
    
        std::priority_queue<Node>q;
        for (int i = 0; i < 10; ++i) {
        
            q.push(Node(std::rand(), std::rand()));
        }
    
        while (!q.empty()){
        
            std::cout << q.top().x << ' ' << q.top().y << std::endl;
            q.pop();
        }
    }

自定义类型重载operator<后，声明对象时就可以只带一个模板参数。

但此时不能像基本类型这样声明priority\_queue<Node,vector,greater >，原因是greater没有定义，如果想用这种方法定义则可以重载operator >。

例子：返回的是小顶堆。但不怎么用，习惯是重载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;
    }

#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的后面）
            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;
    }

[20200716110340947.png]: /images/20230209/05bbaa41ccc248caa1aba62d821b1fe4.png
[20200716110722390.png]: /images/20230209/606d85049c3d42db9b9d4354ecfb65ce.png