關于優先隊列$priority\_queue$大小根堆、重載操作符的說明

一、關于\(priority\_queue\)的說明

内部實作

​

​priority_queue​

​預設情況下，以\(vector\)為底層容器，加上\(heap\)(預設\(max-heap\)) 處理規則；形成大根堆。

\(priority\_queue\)被歸為 \(container\) \(adapter\)，也就是對 \(container\)

​

​priority_queue​

​操作規則上是 \(queue\)，隻允許在尾部加入元素，并從首部取出元素；隻不過内部元素具有優先級，優先級高者先出。

​

​priority_queue​

​的所有元素進出具有一定規則，是以 不提供周遊功能，也不提供疊代器。

疑惑産生

下面為​

​priority_queue​

​的使用規則，第一個傳入了類型，第二個為容器類型，第三個為比較函數。

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>   //comp預設為less
> class priority_queue;      

疑惑關鍵就在于比較函數。

​

​priority_queue​

​預設形成大根堆，而傳入的\(comp\)預設為\(less\)。

為何傳入一個可将序列順序調為有小到大的函數，建成的堆反而是大頂堆呢？

不知你們有沒有這種感覺？直覺上認為傳入\(less\)，建成小頂堆，而傳入\(greater\)，建成大頂堆。

源碼解析

​

​std::less()​

​​源碼：若​

​__x < __y​

​，則傳回\(true\)，順序不變，否則，順序發生變化。這個函數名含義與實作效果相一緻。

struct less : public binary_function<_Tp, _Tp, bool>
{
    _GLIBCXX14_CONSTEXPR
    bool
    operator()(const _Tp& __x, const _Tp& __y) const
    { return __x < __y; }
};      

​

​make_heap​

​​中調用的​

​__push_heap​

​源碼：

__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
            _Distance __topIndex, _Tp __value, _Compare __comp)
    //__holeIndex  新添加節點的索引，即叫做孔洞
    //__topIndex  頂端索引
    //__value   新添加節點的值
    //__comp    比較函數，傳入為less
{
  _Distance __parent = (__holeIndex - 1) / 2;   //找到新節點父節點索引
  while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
      //若孔洞沒有到達最頂端  &&  父節點的值小于新添加節點的值，則要進行下列操作
      //less中，左邊比右邊小則傳回true，與less願意相同
    *(__first + __holeIndex) = *(__first + __parent);   //将父節點的值放入孔洞
    __holeIndex = __parent; //孔洞的索引程式設計了原來父節點的索引，往上移動了
    __parent = (__holeIndex - 1) / 2;   //那麼孔洞的父節點又要繼續往上找
  }
  *(__first + __holeIndex) = __value; //将新添加節點的值放在找到的位置（孔洞）
}      

經過上面源碼分析，傳入的\(comp\)就是為了在比較 孔洞節點 與 父節點 的大小，若傳回\(true\)， 才會進行交換操作 。

是以傳入\(less\)，傳回\(true\)是因為 父節點比孔洞節點小，是以要進行交換，則将大的值移動到前面，是以建成的堆為 大頂堆。

而傳入\(greater\)，傳回\(true\)是因為 父節點 比 孔洞節點大，是以進行交換，則将大的值移動到了後面，是以建成的堆為 小頂堆。

是以，就明白了為什麼傳入\(less\)反而形成了大根堆，而傳入\(greater\)則形成了小根堆。

二、如何使用

#include <queue>
using namespace std;

priority_queue<int> que;    //預設定義了最大堆，等同于将第三個參數使用less<int>
priority_queue<int, vector<int>, less<int>> que;  //定義大根堆

priority_queue<int, vector<int>, greater<int>> que;  //定義小根堆，VS下需要加入頭檔案#include<functional>

//測試 priority_queue<int> que;
que.push(3);
que.push(5);
que.push(4);
cout << que.top() << endl;  //5

//測試 priority_queue<int, vector<int>, less<int>> que;
que.push(3);
que.push(5);
que.push(4);
cout << que.top() << endl;  //5

//測試 priority_queue<int, vector<int>, greater<int>> que;
que.push(3);
que.push(5);
que.push(4);
cout << que.top() << endl;  //3      

三、關于自定義優先級

上面給出了在處理整型等基本資料類型時直接出入\(less\)或者\(greater\)既可以建立相應的大頂堆或者小頂堆。若是處理結構體呢？如何定義優先級呢？

普通資料類型

基本資料類型的比較函數可以直接使用​

​less<int>​

​​或者​

​greater<int>​

​可以滿足建立大根堆或者小根堆。

結構體

對于結構體而言，将結構體放入優先隊列中，比較函數需要建立在針對結構體的具體成員。

自定義優先級的四種方法：

• <以成員函數重載

struct Node {   //我們将Node節點放入優先隊列中希望以value進行比較
    Node(int _id, int _value) : id(_id), value(_value){}
    int id;
    int value;
};

//大根堆
bool operator < (const Node& a, const Node& b){
    return a.value < b.value; //将value的值由大到小排列，形成Node的大根堆
}

int main() {  
    struct Node node1(1, 5);
    struct Node node2(2, 3);
    struct Node node3(3, 4);
    
    priority_queue<Node> que;
    
    que.push(node1);
    que.push(node2);
    que.push(node3);
    
    cout << que.top().value << endl;    //5
}

//小根堆
bool operator < (const Node& a, const Node& b)
{
    return a.value > b.value; //将value的值由小到大排列，形成Node的小根堆
}

cout << que.top().value << endl;    //3      

我試了 ​

​bool operator > ()​

​​，結果會報二進制“<”: 沒有找到接受​

​const Node​

​​類型的左操作數的運算符(或沒有可接受的轉換） 錯誤，我想原因應該是這樣吧：​

​priority_queue​

​​中預設的比較函數為​

​less​

​​，​

​less​

​​函數中隻用到了 ​

​{ return __x < __y; }​

​​，是以重載中若隻重載了​

​>​

​​，函數找不到​

​<​

​，是以會出現錯誤。

struct less : public binary_function<_Tp, _Tp, bool>{
    _GLIBCXX14_CONSTEXPR
    bool
    operator()(const _Tp& __x, const _Tp& __y) const
    { return __x < __y; }
};      

• 自定義比較函數

struct cmp{
    bool operator ()(const Node& a, const Node& b){
        return a.value < b.value;//将value的值由大到小排列，形成Node的大根堆
    }
};
priority_queue<Node, vector<Node>, cmp>q;
cout << que.top().value << endl;    //5

struct cmp{
    bool operator ()(const Node& a, const Node& b){
        return a.value > b.value;//将value的值由小到大排列，形成Node的小根堆
    }
};
priority_queue<Node, vector<Node>, cmp>q;
cout << que.top().value << endl;    //3      

• < 以類成員函數重載

struct Node {    //我們将Node節點放入優先隊列中希望以value進行比較
    Node(int _id, int _value) : id(_id), value(_value){}
    int id;
    int value;
    //大根堆
    bool operator < (const Node& b) const    //注意，此處若沒有const則會報錯
    {
        return value < b.value; //将value的值由大到小排列，形成Node的大根堆
    }
};
cout << que.top().value << endl;  //5      

• <以友元函數重載 【這個和競賽關系不大，暫時不用考慮】

struct Node{
    int id;
    int value;
    friend bool operator<(const Node& a,const Node& b){
        return a.value<b.value;  //按value從大到小排列
    }
};
priority_queue<Node>q;