C++堆的实现：建立和使用堆结构 |21xrx.com

C++堆的实现：建立和使用堆结构

2023-07-13 02:01:44 深夜i -- --

C++ 堆结构实现建立使用

C++堆是一种数据结构，它将一组元素存储在一个有序的二叉树结构中，并且可以通过一些特殊的操作来保证堆的有序性质。在这篇文章中，我们将学习如何建立和使用C++堆结构。

1. 建立堆结构

在C++中，可以使用STL（标准模板库）中提供的priority_queue类来建立堆结构。堆结构默认是大根堆，即根节点的值大于等于所有子节点的值。

示例代码：


#include <queue>
#include <iostream>
using namespace std;
int main() {
  priority_queue<int> q; // 建立一个int类型的大根堆
  q.push(3); // 插入元素3
  q.push(5); // 插入元素5
  q.push(2); // 插入元素2
  q.push(1); // 插入元素1
  cout << "堆中的最大值：" << q.top() << endl; // 输出堆中的最大值，即5
  return 0;
}

在上面的示例代码中，我们首先包含了queue和iostream库。然后，我们使用priority_queue （默认为大根堆）建立了一个堆结构q，并依次插入了元素3、5、2、1。最后，我们使用q.top()来获得堆中的最大值，即5。

2. 堆结构的方法

在C++中，priority_queue类提供了一些特殊的方法来修改和访问堆结构。

2.1 push方法

push方法可以在堆中插入一个元素。

示例代码：


q.push(7); // 在堆中插入元素7

2.2 pop方法

pop方法可以弹出堆顶元素。

示例代码：


q.pop(); // 删除堆顶元素

2.3 top方法

top方法可以访问堆顶元素。

示例代码：


cout << q.top() << endl; // 输出堆顶元素的值

3. 小根堆的建立

如果我们需要建立一个小根堆，可以在建立时指定一个比较函数。比较函数将判断两个元素的大小关系，返回true表示第一个元素比第二个元素小，false表示第一个元素比第二个元素大。

示例代码：


struct cmp {
  bool operator() (int a, int b)
    return a > b; // a小于b返回true
  
};
int main()
  priority_queue<int

在上面的示例代码中，我们定义了一个比较函数cmp，并通过priority_queue , cmp>建立了一个小根堆。这里需要注意，我们使用了第二个参数vector 指定了容器类型，因为建立小根堆需要将元素从大到小排序，而vector容器提供了sort方法。

4. 总结

本文介绍了C++堆的实现方法，包括建立堆结构和使用堆的方法。在使用过程中，我们可以选择建立大根堆或小根堆，并使用push、pop和top方法来修改和访问堆结构。堆结构的应用十分广泛，比如在算法中用来排序、在图论中用来求最短路等等。

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

下一篇: C++中函数的缺省形参值：add()函数示例

评论区

()

相似文章