C++ priority_queue 最大堆、最小堆

C++ priority_queue 最大堆、最小堆

問題描述

通常在刷題的時候，會遇到最大堆、最小堆的問題，這個時候如果自己去實現一個也是OK的，但是通常時間不太夠，那麼如何處理？這時，就可以借助C++ STL的priority_queue。

具體分析

假設有如下一個struct：

struct Node {
    int value;
    int idx;
    Node (int v, int i): value(v), idx(i) {}
    friend bool operator < (const struct Node &n1, const struct Node &n2) ; 
};

inline bool operator < (const struct Node &n1, const struct Node &n2) {
    return n1.value < n2.value;
}

priority_queue pq; // 此時pq為最大堆

如果需要最大堆，則需要如下實現：

struct Node {
    int value;
    int idx;
    Node (int v, int i): value(v), idx(i) {}
//  friend bool operator < (const struct Node &n1, const struct Node &n2) ;
    friend bool operator > (const struct Node &n1, const struct Node &n2) ;
}; 

inline bool operator > (const struct Node &n1, const struct Node &n2) {
    return n1.value > n2.value;
}

priority_queue, greater > pq; // 此時greater會調用 > 方法來確認Node的順序，此時pq是最小堆

其他解決

當然，還有些比較小的較為hack的手段進行。比如要構造一個int類型的最小堆：

priority_queue pq; // 
pq.push( -1 * v1) ; //
pq.push( -1 * v2) ; //
pq.push( -1 * v3) ; // 分別是插入v1, v2, v3變量的相反數，那麼pq其實也就變相成為了最小堆，只是每次從pq取值後，要再次乘以-1即可

struct node{
  int idx;
  int key;
  node(int a=0, int b=0):idx(a), key(b){}
};

struct cmp{
  bool operator()(node a, node b){
    return a.key > b.key;
  }
}; 
priority_queue, cmp> q;