priority_queue使用总结

priority_queue是C++ 中的堆，包含在文件中<queue>中。堆首元素是优先级最高的元素，堆尾元素是优先级最低的元素。priority_queue中的元素可以重复。

使用方法

C++11 中定义如下：

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

所以当不显示指定函数时，优先队列的默认函数为less函数。在STL底层的实现中，如果根节点比插入的节点小时，则进行交换，所以当比较函数为less时，优先队列为大根堆，反之则是小根堆；

自定义比较类型

对于非标准类型的优先队列，需要自定义比较函数。在自定义比较函数时，与sort函数不同（sort函数要求一个返回bool的函数即可），优先队列的自定义比较函数需要为一个重载了<操作符的类或一个比较类，在该类中重载小括号()。这里是因为STL中默认的比较函数使用的是<,所以当重载操作符时，应该使用<号；

struct Node {   //我们将Node节点放入优先队列中希望以value进行比较
    Node(int _id, int _value) : id(_id), value(_value){}
    int id;
    int value;
};

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
}

1.自定义比较函数

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

2.重载<操作符

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