c++ 优先队列 小根堆

在C++中，优先队列默认是大根堆，也就是说，队列中的元素按照从大到小的顺序排列。如果想要使用小根堆，需要在定义优先队列时指定底层容器类型为vector，比较函数为greater。下面是一个小根堆的例子：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> q;
    q.push(3);
    q.push(5);
    q.push(1);
    while(!q.empty()) {
        cout << q.top() << endl;
        q.pop();
    }
    return 0;
}

在这个例子中，我们使用了STL自带的小根堆，因此需要将vector改为greater<int>。其中，vector<int>是指底层容器的类型，而greater<int>是指比较函数对象的类型。

另外，如果想要使用自定义类型的小根堆，需要在定义结构体时重载小于号运算符，如下所示：

struct cs {
    int x;
    bool operator < (const cs &rhs) const {
        return x > rhs.x;
    }
} a;
priority_queue<cs> Q;

这样就可以使用自定义类型的小根堆了。