priority_queue

基本用法

1. 需要包含头文件 <queue>
2. 常用函数

priority_queue<int> q1;     //大顶堆
priority_queue<int, vector<int>, less<int>> q2; //等价于q1, 大顶堆
priority_queue<int, vector<int>, greator<int>> q3; //小顶堆
q.top();//取队列首元素，也就是堆顶元素
q.empty();//判断队列是否为空
q.size();//返回队列的元素个数
q.push(1);//向优先队列中插入一个元素
q.pop();//弹出队列头元素

自定义比较函数

如果自定义结构体需要使用优先级队列，则必须提供比较函数，比较函数常用两种方式1.重载运算符 2.自定义比较函数的方式

struct Node{
    int x, y;
    Node(){}
    Node(int x, int y) : x(x), y(y) {}

    //重载运算符
    bool operator< (const Node& t) const {
        if(x != t.x){
            return x < t.x ? true : false;
        } else {
            return y <= t.y ? true : false;
        }
    }
};

// 小顶堆比较函数
struct cmp2{
    bool operator()(const Node& a, const Node& b){
        if(a.x != b.x){
            return a.x < b.x ? false : true;
        } else {
            return a.y <= b.y ? false : true;
        }
    }
};

int main()
{

    //大顶堆
    //priority_queue<Node> q;

    // 小顶堆
    priority_queue<Node, vector<Node>, cmp2> q;
    for(int i = 0; i < 10; i++){
        Node t(i, 2*i);
        q.push(t);
    }

    while(q.size()){
        cout << "x=" << q.top().x << ", y=" << q.top().y << endl;
        q.pop();
    }

    return 0;
}