关于优先队列那点事

以你之姓@ 2022-08-23 11:58 212阅读 0赞

在优先队列中，优先级高的元素先出队列。

标准库默认使用元素类型的   <   操作符来确定它们之间的优先级关系。

1.用法一

priority_queue<int> qi;

通过 < 操作符可知在整数中元素大的优先级高

2.用法二

priority_queue<int, vector<int>, greater<int> >qi2;

如果我们需要从小到大输出，则可以使用functional.h函数对象作为比较函数，传入一个函数。

代码中，第二个参数为容器类型，第三个参数为比较函数。

3.用法三

struct node
    {
        friend bool operator< (node n1, node n2)
        {
            return n1.priority < n2.priority;
        }
        int priority;
        int value;
    };

在该结构中，通过自定义operator < 操作符来比较元素中的优先级。

#include<stdio.h>  
    #include<functional>  
    #include<queue>  
    #include<vector>  
    using namespace std;  
    //定义结构，使用运算符重载,自定义优先级1  
    struct cmp1{  
        bool operator ()(int &a,int &b){  
            return a>b;//最小值优先  
        }  
    };  
    struct cmp2{  
        bool operator ()(int &a,int &b){  
            return a<b;//最大值优先  
        }  
    };  
    //定义结构，使用运算符重载,自定义优先级2  
    struct number1{  
        int x;  
        bool operator < (const number1 &a) const {  
            return x>a.x;//最小值优先  
        }  
    };  
    struct number2{  
        int x;  
        bool operator < (const number2 &a) const {  
            return x<a.x;//最大值优先  
        }  
    };  
    int a[]={14,10,56,7,83,22,36,91,3,47,72,0};  
    number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0};  
    number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0};  
      
    int main()  
    {   priority_queue<int>que;//采用默认优先级构造队列  
      
        priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
        priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
      
        priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误，  
                                                          //这是右移运算符，所以这里用空格号隔开  
        priority_queue<int,vector<int>,less<int> >que4;最大值优先  
      
        priority_queue<number1>que5;  
        priority_queue<number2>que6;  
      
        int i;  
        for(i=0;a[i];i++){  
            que.push(a[i]);  
            que1.push(a[i]);  
            que2.push(a[i]);  
            que3.push(a[i]);  
            que4.push(a[i]);  
        }  
        for(i=0;num1[i].x;i++)  
            que5.push(num1[i]);  
        for(i=0;num2[i].x;i++)  
            que6.push(num2[i]);  
      
      
        printf("采用默认优先关系:\n(priority_queue<int>que;)\n");  
        printf("Queue 0:\n");  
        while(!que.empty()){  
            printf("%3d",que.top());  
            que.pop();  
        }  
        puts("");  
        puts("");  
      
        printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n");  
        printf("Queue 1:\n");  
        while(!que1.empty()){  
            printf("%3d",que1.top());  
            que1.pop();  
        }  
        puts("");  
        printf("Queue 2:\n");  
        while(!que2.empty()){  
            printf("%3d",que2.top());  
            que2.pop();  
        }  
        puts("");  
        puts("");  
        printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n");  
        printf("Queue 3:\n");  
        while(!que3.empty()){  
            printf("%3d",que3.top());  
            que3.pop();  
        }  
        puts("");  
        printf("Queue 4:\n");  
        while(!que4.empty()){  
            printf("%3d",que4.top());  
            que4.pop();  
        }  
        puts("");  
        puts("");  
        printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n");  
        printf("Queue 5:\n");  
        while(!que5.empty()){  
            printf("%3d",que5.top());  
            que5.pop();  
        }  
        puts("");  
        printf("Queue 6:\n");  
        while(!que6.empty()){  
            printf("%3d",que6.top());  
            que6.pop();  
        }  
        puts("");  
        return 0;  
    }

声明：上述文章参考了

[没有代码的日子][Link 1] [http://blog.chinaunix.net/uid-21712186-id-1818266.html][http_blog.chinaunix.net_uid-21712186-id-1818266.html][skyli][]  [http://www.cppblog.com/shyli/archive/2007/04/06/21366.html][http_www.cppblog.com_shyli_archive_2007_04_06_21366.html]  
  
C++之梦

[Link 1]: http://blog.chinaunix.net/uid/21712186.html
[http_blog.chinaunix.net_uid-21712186-id-1818266.html]: http://blog.chinaunix.net/uid-21712186-id-1818266.html
[skyli]: http://www.cppblog.com/shyli/
[http_www.cppblog.com_shyli_archive_2007_04_06_21366.html]: http://www.cppblog.com/shyli/archive/2007/04/06/21366.html