首页 > 代码库 > 使用priority_queue建立小顶推

使用priority_queue建立小顶推

2024-07-24 15:40:50   212人阅读

template < 
   class Type,  
   class Container=vector<Type>, 
   class Compare=less<typename Container::value_type>  
> 
class priority_queue

注意，priority_queue是一个模板类，它的定义形式如上;其中，它的每一个参数也是一个类，这里我们主要解释一下Compare 参数。

其中，Compare 参数是一个类，里面的比较函数决定了堆是大顶堆还是小顶堆。一般而言, 默认是大顶堆。但是，在某些情况下，我们需要一个固定大小的小顶堆（比如要寻找某个集合中最大的两个元素。

现在，我们再看一下其中的less模板类：
template <class T> struct less {
  bool operator() (const T& x, const T& y) const {return x<y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

其中，里面最关键的是一个()操作符。

这里，我们给出一个例子：
struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}
};
 
struct cmp{
    bool operator() ( Node a, Node b ){
        if( a.x== b.x ) return a.y> b.y;
         
        return a.x> b.x; }
};
 
    priority_queue<Node, vector<Node>, cmp> q;
注意，这个堆是小顶堆。实际上，我们是按照operator ()的操作，将新添加的元素放在堆底的。

使用priority_queue建立小顶推


联系
我们