STL模板库之优先队列的用法

向右看齐 2022-05-12 13:50 155阅读 0赞

一般只有一个数的队列优先排序的代码如下（很简单）

#include<iostream>
    #include<functional>
    #include<queue>
    #include<vector>
    
    using namespace std;
    
    int main()
    {
        const int len = 5;
        int i;
        int a[len];
        for (i=0;i<len;i++){
            cin>>a[i];
        }
        priority_queue<int> qi;
        for(i = 0; i < len; i++)
            qi.push(a[i]);
    
        for(i = 0; i < len; i++)
        {
            cout<<qi.top()<<" "<<endl;
            qi.pop();
        }
        cout<<endl;
        return 0;
    }

上述定义默认是按照最大值为首进行排列的，若需要最小值进行排列，可按照如下定义：

priority\_queue<int, vector<int>, greater<int> > qi;

接下来依旧是有关结构体指针的使用方法

首先是对结构体进行排序

#include<iostream>
    #include<functional>
    #include<queue>
    #include<vector>
    using namespace std;
    struct node
    {
        friend bool operator< (node n1, node n2)
        {
            return n1.priority < n2.priority;
        }
        int priority;
        int value;
    };
    
    
    int main()
    {
        const int len = 5;
        int i;
        
        node a[len];
        for (i=0;i<len;i++){
            cin>>a[i].priority>>a[i].value;
        }
    
        priority_queue<node > qi;
        for(i = 0; i < len; i++)
            qi.push(a[i]);
        for(i = 0; i < len; i++)
        {
            cout<<qi.top().priority<<" "<<qi.top().value<<" "<<endl;
            qi.pop();
        }
        cout<<endl;
       
        return 0;
    }
    /*  6 1
        9 4
        2 3
        8 8
        1 2*/

其次是对结构体指针进行排序

因为结构体指针与结构体是不同的东东，所以不能仅在结构体写一个友元函数进行比较，需要用下述方法下能使得优先队列排序成功

#include<iostream>
    #include<queue>
    #include<vector>
    using namespace std;
    
    class Comapre;
    class node{
        friend Comapre;
        public:
         int cp;//当前价值
         int cw;//当前重量
         int up;//优先级
         int i;
         node *parent;
         node *left;
         node *right;
         node(int up1=0,int i1=0,node *p=NULL){
           cw=0;
           cp=0;
           up=up1;
           i=i1;
           parent=p;
           left=right=NULL;
         }
          bool lessthan (const node* node) const
    	{
    		return up< node->up;
    	}
    };
    class Comapre
    {
    public:
    	bool operator () (node*node1,node*node2)
    	{
    		return node1->lessthan(node2);
    	}
    };
    int main()
    {
        const int len = 5;
        int i;
    
        priority_queue<node*,vector<node*>,Comapre>qn;
        node *b;
        int a,c;
        for(i=0;i<len;i++){
           cin>>a>>c;
           b=new node(a,c);
           qn.push(b);
        }
    
        cout<<"优先级"<<'\t'<<"值"<<endl;
        for(i = 0; i < len; i++)
        {
            cout<<qn.top()->up<<'\t'<<qn.top()->i<<endl;
            qn.pop();
        }
        return 0;
    }
      /*6 1
        9 4
        2 3
        8 8
        1 2*/