C++实现小根堆：详细教程 |21xrx.com

C++实现小根堆：详细教程

2023-07-10 15:02:20 深夜i -- --

C++ 小根堆实现教程详细

小根堆是一种可以在 O(log n) 时间内查找到堆顶最小值的数据结构。C++中可以用STL的priority_queue模板类实现小根堆，不过这里我们重点学习如何手写实现小根堆。

首先，我们需要定义一个结构体来表示小根堆的节点，包含两个成员变量：元素值 value 和该元素在数组中的下标 index。


struct Node
  int value;   
  int index;
;

接着，我们需要定义一个类 MinHeap，它包含用于维护小根堆的成员函数和私有变量。在 MinHeap 类中，我们定义一个 vector 类型的数组 heap 来存储元素，以及一个函数 min_heapify 来维护小根堆的性质。


class MinHeap {
public:
  MinHeap();          
  void insert(int value);   
  void removeMin();      
  int getMin() const;     
  bool isEmpty() const;    
private:
  vector<Node> heap;     
  void min_heapify(int index);
};

接下来，我们逐一实现 MinHeap 类中的成员函数。

构造函数 MinHeap()：它没有参数，所以直接将 heap 数组初始化为空。


MinHeap::MinHeap() {}

成员函数 insert(int value)：我们首先将一个新节点（即一个元素值和元素下标）插入到 heap 数组中最后一个位置，然后更新堆。更新堆的方法是不断将新插入的节点与该节点的父节点进行比较，如果插入的元素小于父节点，则交换二者位置。这样，该节点可能就上移到了更高的层次，最终再循环遍历至根节点，也就是小根堆的堆顶。


void MinHeap::insert(int value) {
  Node node;
  node.value = value;
  node.index = heap.size();
  heap.push_back(node);
  int child = heap.size() - 1;
  int parent = (child - 1) / 2;
  while (child > 0 && heap[parent].value > heap[child].value) {
    swap(heap[child], heap[parent]);
    child = parent;
    parent = (child - 1) / 2;
  }
}

函数 removeMin()：该函数用于移除堆顶元素，也就是 heap[0]。待移除的元素应该是最小的，所以移除堆顶节点之后，将最后一个节点移到堆顶位置，然后更新堆。更新堆的方法是从该节点开始，与其两个子节点比较，将值较小的节点与该节点交换位置，然后遍历下一层，直到没有子节点需要交换。


void MinHeap::removeMin() {
  if (heap.empty()) return;
  int size = heap.size();
  heap[0] = heap[size-1];
  heap.pop_back();
  min_heapify(0);
}

函数 getMin()：该函数用于返回堆顶元素的值。因为小根堆的堆顶元素就是值最小的节点，所以该节点的 value 值即为所求。


int MinHeap::getMin() const {
  if (heap.empty()) return -1;
  return heap[0].value;
}

函数 isEmpty()：该函数用于判断小根堆是否为空，如果 heap 数组为空，则代表小根堆里没有任何元素。


bool MinHeap::isEmpty() const {
  return heap.empty();
}

最后，我们来实现一下用于维护小根堆性质的函数 min_heapify。该函数的作用是在将一个新元素加入堆以后，从该元素向下遍历，将该节点和其子节点比较，如果子节点的值小于该节点，则交换二者位置。代码如下：


void MinHeap::min_heapify(int index) {
  int left_child = 2 * index + 1;
  int right_child = 2 * index + 2;
  int smallest = index;
  if (left_child < heap.size() && heap[left_child].value < heap[smallest].value) {
    smallest = left_child;
  }
  if (right_child < heap.size() && heap[right_child].value < heap[smallest].value) {
    smallest = right_child;
  }
  if (smallest != index) {
    swap(heap[index], heap[smallest]);
    min_heapify(smallest);
  }
}

到此为止，我们就完成了小根堆的手写实现。通过实现这些函数，我们可以利用小根堆来解决许多数据结构上的问题。

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

下一篇: C++中使用Map数组导致崩溃问题

评论区

()

相似文章