C++中如何定义小根堆？ |21xrx.com

2023-06-25 22:09:03 深夜i -- --

C++ 小根堆定义

小根堆是一种常用的数据结构，能够快速地找到最小值。在C++中，可以通过使用STL中的priority_queue轻松实现小根堆。

定义小根堆需要做以下几个步骤：

1. 包含头文件

通过#include 来包含头文件，STL的priority_queue需要这个头文件支持。

2. 定义比较函数

在定义priority_queue时，需要定义一个比较函数，用于堆排序中，如何比较元素的大小。

比如，如果要定义一个存放整数的小根堆，可以这样定义：


struct cmp {
  bool operator()(const int& a, const int& b)
    return a > b;
  
};
priority_queue<int, vector<int>, cmp> q;

这个代码是定义了一个结构体cmp，它重载了()运算符。在()运算符中，比较传入的两个参数a和b的大小，如果a小于b，则返回true，否则返回false。注意这里返回true，说明a在堆中应该排在b前面，保证小的元素在堆的前面。

3. 定义priority_queue

定义priority_queue模板类时，需要指定元素类型、使用的容器类型和比较函数类型。

比如，上面的cmp结构体可以这样使用：


priority_queue<int, vector<int>, cmp> q;

这里指定元素类型为int，容器类型为vector，比较函数类型为自定义的结构体cmp。

4. 插入元素

定义了priority_queue之后，就可以使用push()函数向堆中插入元素。比如：


q.push(3);
q.push(1);
q.push(5);
q.push(4);

push()函数是插入元素到队列中的函数，将元素插入到上述定义的小根堆中。

5. 访问堆顶元素

通过top()函数，可以获取小根堆中最小的元素，比如：


cout << q.top(); // 输出：1

6. 弹出堆顶元素

通过pop()函数，可以将小根堆中最小的元素弹出。比如：


q.pop(); // 弹出堆顶元素1

通过上述步骤，就可以在C++中定义小根堆。小根堆在实际开发中有着广泛的应用，比如在Dijkstra算法中，使用小根堆可以优化算法的时间复杂度。

上一篇: idea打包java可执行jar包

下一篇: C++程序编写中可能出现的include错误

()

相似文章