c++STL库小根堆

你好！关于C++的STL库中的小根堆（min heap），你可以使用priority_queue容器来实现。priority_queue是STL库中的一个容器适配器，它会根据元素的优先级自动进行排序。

下面是一个使用priority_queue实现小根堆的示例代码：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 向小根堆中插入数据
    minHeap.push(5);
    minHeap.push(2);
    minHeap.push(10);    minHeap.push(3);

    // 输出小根堆中的数据
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}

在上面的代码中，我们创建了一个priority_queue对象minHeap，并指定了第三个模板参数为std::greater<int>，这样就可以实现小根堆的功能。然后，我们使用push函数向小根堆中插入数据，使用top函数取出堆顶元素，并使用pop函数删除堆顶元素。

希望对你有所帮助！如有更多问题，请继续提问。

相关问题

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;

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

c++优先队列小根堆

C++中的优先队列默认是大根堆，如果要使用小根堆，可以通过以下两种方式实现：

1. 自定义比较函数

在创建优先队列时，可以自定义比较函数，使其按照小根堆的方式进行排序。比较函数需要返回一个bool类型的值，表示两个元素的大小关系。

#include <queue>
using namespace std;

struct cmp{
    bool operator()(int a, int b){
        return a > b; // 小根堆，a比b小返回true
    }
};

int main(){
    priority_queue<int, vector<int>, cmp> pq;
    pq.push(5);
    pq.push(2);
    pq.push(7);
    while(!pq.empty()){
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

2. 使用greater模板类

STL中提供了一个greater模板类，可以用来定义小根堆。在定义优先队列时，将比较函数的类型设置为greater<T>即可。

#include <queue>
using namespace std;

int main(){
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(5);
    pq.push(2);
    pq.push(7);
    while(!pq.empty()){
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}