C++ 优先队列应用方法浅析

﹏ヽ暗。殇╰゛Y 2022-08-02 09:54 122阅读 0赞

【摘要】

> 本文从两个方面介绍优先队列，1.优先队列的常见函数；2.优先队列代码实现：堆排序和哈夫曼树。

【正文】

一.优先队列函数列表

>  *  empty() 如果优先队列为空，则返回真 
>  *  pop() 删除第一个元素 
>  *  push() 加入一个元素 
>  *  size() 返回优先队列中拥有的元素的个数 
>  *  top() 返回优先队列中有最高优先级的元素

二.优先队列代码用例

示例1 
    #include <iostream>  
    #include <queue>  
    #include <deque>  
    #include <vector>  
    #include <functional>  
    using namespace std;  
      
    #if _MSC_VER > 1020 // if VC++ version is > 4.2  
     using namespace std; // std c++ libs implemented in std  
     #endif  
      
    // Using priority_queue with deque  
    // Use of function greater sorts the items in ascending order  
    typedef deque<int, allocator<int> > INTDQU;  
    typedef priority_queue<int,INTDQU, greater<int> > INTPRQUE;  
      
    // Using priority_queue with vector  
    // Use of function less sorts the items in descending order  
    typedef vector<char, allocator<char> > CHVECTOR;  
    typedef priority_queue<char,CHVECTOR,less<char> > CHPRQUE;  
      
    void main(void)  
    {  
      
     int size_q;  
     INTPRQUE q;  
     CHPRQUE p;  
      
     // Insert items in the priority_queue(uses deque)  
     q.push(42);  
     q.push(100);  
     q.push(49);  
     q.push(201);  
      
     // Output the item at the top using top()  
     cout << q.top() << endl;  
     // Output the size of priority_queue  
     size_q = q.size();  
     cout << "size of q is:" << size_q << endl;  
     // Output items in priority_queue using top()  
     // and use pop() to get to next item until  
     // priority_queue is empty  
     while (!q.empty())  
     {  
     cout << q.top() << endl;  
     q.pop();  
     }  
      
    // Insert items in the priority_queue(uses vector)  
     p.push('c');  
     p.push('a');  
     p.push('d');  
     p.push('m');  
     p.push('h');  
      
     // Output the item at the top using top()  
     cout << p.top() << endl;  
      
     // Output the size of priority_queue  
     size_q = p.size();  
     cout << "size of p is:" << size_q << endl;  
      
     // Output items in priority_queue using top()  
     // and use pop() to get to next item until  
     // priority_queue is empty  
     while (!p.empty())  
     {  
     cout << p.top() << endl;  
     p.pop();  
     }  
    }

>     输出结果：  
>     42   
>     size of q is:4   
>     42   49   100   201   
> 
>     m  
>     size of p is:5  
>     m   h   d   c  a

示例2
    #include<iostream>  
    #include<queue>  
    using namespace std;  
    struct cmp  
    {  
     bool operator()(const int &a,const int &b)  
      
     {  
     return a<b;//按升序排序  
      
     }  
    };  
    typedef priority_queue< int, vector<int>, cmp > qu;  
    void main()  
    {  
     qu p;  
     p.push(42);  
     p.push(100);  
     p.push(49);  
     p.push(201);  
     while (!p.empty())  
     {  
     cout << p.top() << endl;  
     p.pop();  
     }  
    }

>     输出结果：   
>     201   100   49   42

示例3(用priority_queue实现哈夫曼树)：
    #include<iostream>  
    #include<queue>  
    using namespace std;  
    class Node   
    {  
    public:  
     int weight;  
     Node* left;  
     Node* right;  
     Node(int w, Node* l, Node* r): weight(w), left(l), right(r) {}  
     Node(int w): weight(w), left(NULL), right(NULL) {}  
    };  
      
    class cmp //用于priority_queue的仿函数类  
    {  
     public :  
     bool operator()(Node* a,Node* b)  
      
     {  
     return a->weight>=b->weight;  
     }  
    };  
      
    //传入的是指针，如果用对象去实现，你就不知道左右指针的指向了  
      
    //中序遍历  
    void InOrder(Node* p)   
    {  
     if (p != NULL)   
     {  
     InOrder(p->left);  
     cout<<p->weight<<'/t';  
     InOrder(p->right);  
     }  
    }  
      
    void freeTree(Node* p)//销毁二叉树  
    {  
    if(p->left!=NULL)  
     freeTree(p->left);  
    if(p->right!=NULL)  
     freeTree(p->right);  
    delete(p);  
    }  
      
    int main()  
    {  
     Node* m1,*m2;  
     priority_queue<Node*,vector<Node*>,cmp> q;  
     for(int i=0;i<6;++i)//6个节点   
     {  
     int n=rand()%100;  
     q.push(new Node(n));//权值随机产生   
     cout<<n<<'/t';   
     }  
     cout<<endl;  
     for(int j=1;j<6;++j)//合并5次   
     {  
     m1=q.top(); q.pop();  
     m2=q.top(); q.pop();  
     int w=m1->weight+m2->weight;  
     q.push(new Node(w,m1,m2));  
     }  
     Node* root=q.top();  
     InOrder(root);  
     cout<<endl;  
     freeTree(root);  
      
     system("pause");  
     return 0;  
    }

输出结果：  
    41 67 34 0 69 24  
    41 99 0 24 24 58 34 235 67 136