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

C++如何定义小根堆

2023-07-05 09:52:18 深夜i -- --

C++ 小根堆定义

在C++中，小根堆是一种常见的数据结构，用于快速查找最小值。小根堆可以通过定义一个类来实现，下面是实现小根堆的代码示例：


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class MinHeap {
public:
  MinHeap() {}
  void push(int num) {
    min_heap.push(num);
  }
  void pop() {
    min_heap.pop();
  }
  int top() {
    return min_heap.top();
  }
  bool empty() {
    return min_heap.empty();
  }
private:
  priority_queue<int, vector<int>, greater<int>> min_heap;
};
int main() {
  MinHeap heap;
  heap.push(5);
  heap.push(2);
  heap.push(7);
  heap.push(3);
  while (!heap.empty()) {
    cout << heap.top() << endl;
    heap.pop();
  }
  return 0;
}

在上面的代码中，我们定义了一个名为MinHeap的类，其中包含了push、pop、top和empty这些方法。其中，push方法用于往小根堆中插入元素，pop方法用于弹出小根堆中的最小值，top方法用于获取小根堆中的最小值，empty方法则用于判断小根堆是否为空。

在MinHeap类中，我们使用了一个名为min_heap的优先队列，它是一个基于堆的数据结构，其中包含了一个vector容器和一个比较器，比较器用于比较两个元素的大小。在我们的实现中，我们指定了一个比较器greater ，用于表示我们需要一个小根堆。

在main函数中，我们创建了一个MinHeap实例heap，并插入了一些测试数据。然后，我们不断地从heap中弹出最小值，直到heap为空为止。

综上所述，我们可以看出，C++定义小根堆非常简单，只需要定义一个包含优先队列的类即可。通过对堆的操作，我们可以快速、高效地实现对最小值的查找。

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

下一篇: 将C++代码封装成库文件

评论区

()

相似文章