问题描述

通常在刷题的时候，会遇到最大堆、最小堆的问题，这个时候如果自己去实现一个也是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;