閱讀62 返回首頁    go 阿裏雲 go 技術社區[雲棲]

[算法係列之四]優先級隊列

【概念】

優先級隊列，顧名思義，就是一種根據一定優先級存儲和取出數據的隊列。它可以說是隊列和排序的完美結合體，不僅可以存儲數據，還可以將這些數據按照我們設定的規則進行排序。優先級隊列是堆的一種常見應用。有最大優先級隊列（最大堆）和最小優先級隊列（最小堆）。優先級隊列是一種維護有一組元素構成的集合S的數據結構。

【優先隊列支持的基本運算】

  1. //建立一個保存元素為int的優先級隊列，其實是建了一個小頂堆  
  2. //但是請特別注意這樣的建的堆默認是大頂堆，即我們從堆頂去的元素是整個堆中元素最大的。  
  3.   
  4. priority_queue<int> Heap;  
  5.   
  6. //可以這樣建一個表示小頂堆的優先級隊列  
  7.   
  8. priority_queue<int , vector<int>, greater<int> > Heap;  
  9.   
  10. //將元素x放入優先級隊列中  
  11.   
  12. Heap.push(x);  
  13.   
  14. //取出優先級隊列第一個元素(堆頂元素),保存在x中  
  15.   
  16. int x = Heap.top();  
  17.   
  18. //彈出堆頂元素，取出後堆會自動調整為一個最小堆（最大堆）  
  19.   
  20. Heap.pop();  
  21.   
  22. //判斷是否為空  
  23.   
  24. Heap.empty();  
  25.   
  26. //頭文件  
  27.   
  28. #include<queue>  

【原理】

priority_queue調用 STL裏麵的 make_heap(), pop_heap(), push_heap() 算法實現，也算是堆的另外一種形式。

用make_heap(), pop_heap(), push_heap() 簡單實現一個最大優先級隊列

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   題目: 簡單實現最大優先級隊列
*   博客：
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//簡單實現最大優先級隊列
template<typename T>
class priority_queue{
private:
    // 數據
    vector<T> data;
public:
    // 進隊列
    void push(T val){
        data.push_back(val);
        push_heap(data.begin(),data.end());
    }
    // 出隊列
    void pop(){
        pop_heap(data.begin(),data.end());
        data.pop_back();
    }
    // 頭元素
    T top(){
        return data.front();
    }
    // 大小
    int size(){
        return data.size();
    }
    // 是否為空
    bool empty(){
        return data.empty();
    }
};

int main(){
    priority_queue<char> heap;
    heap.push('5');
    heap.push('4');
    heap.push('3');
    heap.push('9');
    heap.push('6');
    while(!heap.empty()){
        cout<<heap.top()<<endl;
        heap.pop();
    }//while
}

STL裏麵的 priority_queue 寫法與此相似，隻是增加了模板及相關的迭代器什麼的。 

priority_queue 對於基本類型的使用方法相對簡單。他的模板聲明帶有三個參數:
priority_queue<Type, Container, Functional>
其中Type 為數據類型， Container 為保存數據的容器，Functional 為元素比較方式。
Container 必須是用數組實現的容器，比如 vector, deque 但不能用 list.
STL裏麵默認用的是 vector. 比較方式默認用 operator< , 所以如果你把後麵倆個參數缺省的話，
優先隊列就是大頂堆，隊頭元素最大。 

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<char> heap;
    heap.push('5');
    heap.push('4');
    heap.push('3');
    heap.push('9');
    heap.push('6');
    // 輸出最大優先級隊列
    while(!heap.empty()){
        cout<<heap.top()<<endl;
        heap.pop();
    }//while
}

如果要用到小頂堆，則一般要把模板的三個參數都帶進去。
STL裏麵定義了一個仿函數 greater<>，對於基本類型可以用這個仿函數聲明小頂堆

#include <iostream>
#include <queue>
using namespace std;

int main(){
    // 最小優先級隊列
    priority_queue<char,vector<char>,greater<char> > heap;
    heap.push('5');
    heap.push('4');
    heap.push('3');
    heap.push('9');
    heap.push('6');
    // 輸出最大優先級隊列
    while(!heap.empty()){
        cout<<heap.top()<<endl;
        heap.pop();
    }//while
}

對於自定義類型，則必須自己重載 operator< 或者自己寫仿函數

【自定義優先級】

重載 operator<

  1. #include<iostream>  
  2. #include<stdio.h>  
  3. #include<queue>  
  4. using namespace std;  
  5.   
  6. struct Node    
  7. {    
  8.     //值  
  9.     int value;  
  10.     //編號  
  11.     int key;    
  12.     //重載操作符  
  13.     friend bool operator < (Node node1,Node node2)    
  14.     {      
  15.         //最大優先隊列  
  16.         return node1.value < node2.value;    
  17.     }  
  18.     /* 
  19.     不要重載這個'>'隻重載'<' 
  20.     friend bool operator > (Node node1,Node node2)   
  21.     {   
  22.         return node1.value > node2.value;   
  23.     }  
  24.     */  
  25. };  
  26.   
  27. struct Node2    
  28. {    
  29.     //值  
  30.     int value;  
  31.     //編號  
  32.     int key;    
  33.     //重載操作符  
  34.     friend bool operator < (Node2 node1,Node2 node2)    
  35.     {      
  36.         //最小優先隊列  
  37.         return node1.value > node2.value;    
  38.     }  
  39. };  
  40.   
  41. int main(){  
  42.     int i;  
  43.     //實例一 結構體1  
  44.     Node b[5];  
  45.     b[0].value = 6; b[0].key = 1;   
  46.     b[1].value = 9; b[1].key = 2;   
  47.     b[2].value = 2; b[2].key = 3;   
  48.     b[3].value = 8; b[3].key = 4;   
  49.     b[4].value = 1; b[4].key = 5;   
  50.     //最大優先隊列  
  51.     priority_queue<Node> Heap;  
  52.     //入隊列  
  53.     for(i = 0;i < 5;i++){  
  54.         Heap.push(b[i]);  
  55.     }  
  56.     printf("最大優先隊列：\n");  
  57.     //出隊列  
  58.     for(i = 0;i < 5;i++){  
  59.         printf("key:%d value:%d\n",Heap.top().key,Heap.top().value);  
  60.         Heap.pop();  
  61.     }  
  62.     //實例二 結構體2  
  63.     Node2 b2[5];  
  64.     b2[0].value = 6; b2[0].key = 1;   
  65.     b2[1].value = 9; b2[1].key = 2;   
  66.     b2[2].value = 2; b2[2].key = 3;   
  67.     b2[3].value = 8; b2[3].key = 4;   
  68.     b2[4].value = 1; b2[4].key = 5;   
  69.     //最大優先隊列  
  70.     priority_queue<Node2> Heap2;  
  71.     //入隊列  
  72.     for(i = 0;i < 5;i++){  
  73.         Heap2.push(b2[i]);  
  74.     }  
  75.     printf("最小優先隊列：\n");  
  76.     //出隊列  
  77.     for(i = 0;i < 5;i++){  
  78.         printf("key:%d value:%d\n",Heap2.top().key,Heap2.top().value);  
  79.         Heap2.pop();  
  80.     }  
  81.     return 0;  
  82. }  



注意：

  1. struct Node    
  2. {    
  3.     //值  
  4.     int value;  
  5.     //編號  
  6.     int key;    
  7.     friend bool operator > (Node node1,Node node2)    
  8.     {    
  9.         return node1.value > node2.value;    
  10.     }   
  11. };  

這樣會報錯。因為標準庫默認使用元素類型的<操作符來確定它們之間的優先級關係。


自定義類型重載 operator< 後，聲明對象時就可以隻帶一個模板參數。
但此時不能像基本類型這樣聲明priority_queue<Node, vector<Node>, greater<Node> >;
原因是 greater<Node> 沒有定義，如果想用這種方法定義則可以按如下方式:

#include <iostream>
#include <queue>
using namespace std;

struct Node{
    int value;
    int key;
    Node(int x,int y):key(x),value(y){}
};

struct cmp{
    bool operator()(Node a,Node b){
        if(a.key == b.key){
            return a.value > b.value;
        }
        return a.key > b.key;
    }
};

int main(){

    priority_queue<Node,vector<Node>,cmp> heap;
    Node node0(5,6);
    Node node1(3,3);
    Node node2(2,4);
    Node node3(2,3);
    Node node4(1,3);

    heap.push(node0);
    heap.push(node1);
    heap.push(node2);
    heap.push(node3);
    heap.push(node4);

    while(!heap.empty()){
        Node node = heap.top();
        cout<<"Key->"<<node.key<<" Value->"<<node.value<<endl;
        heap.pop();
    }//while
}



具體實例：點擊打開鏈接

                   看病要排隊

                   搬水果

最後更新：2017-04-03 12:56:30

  上一篇：go HDU1251-統計難題
  下一篇：go 扯談網絡編程之自己實現ping