C++实现小顶堆 |21xrx.com

C++实现小顶堆

2023-07-05 18:25:03 深夜i -- --

C++ 小顶堆实现

小顶堆是一种常见的数据结构，具有很多应用场景，比如在算法实现中进行排序和查找最小的元素等。C++作为一门面向对象的编程语言，提供了很多方便的数据结构和模板，可以很方便地实现小顶堆。

首先，我们需要定义一个小顶堆类，其中包含一个数组作为存储容器，以及一些操作方法，比如插入元素和获取堆顶元素等。下面是一个简单的定义：


class MinHeap {
public:
  MinHeap(int capacity);
  ~MinHeap();
  void insert(int val);
  int pop();
  int peek();
private:
  int* heap_;
  int size_;
  int capacity_;
  void sift_up(int index);
  void sift_down(int index);
};

在这个定义中，MinHeap类包含一个元素类型为int的数组heap_，用来存储堆中的元素。size_表示堆的当前大小，capacity_表示堆的容量大小。sift_up和sift_down两个私有方法分别用来实现堆操作中的上浮和下沉。

接下来是插入元素的代码实现：


void MinHeap::insert(int val) {
  if (size_ == capacity_)
    return;
  
  heap_[size_] = val;
  sift_up(size_);
  size_++;
}

在这个实现中，我们首先检查堆是否已满，如果已满则直接返回。然后将新元素添加到堆的末尾，接着进行上浮操作将堆中新元素调整到正确的位置。

下面是获取堆顶元素的代码实现：


int MinHeap::peek() {
  if (size_ == 0)
    return -1; // 堆为空
  
  return heap_[0];
}

在这个实现中，我们首先检查堆的大小是否为0，如果为0则说明堆为空，返回-1表示失败。否则，返回堆顶元素即可。

最后是删除堆顶元素的代码实现：


int MinHeap::pop() {
  if (size_ == 0)
    return -1; // 堆为空
  
  int ret = heap_[0];
  heap_[0] = heap_[size_ - 1];
  size_--;
  sift_down(0);
  return ret;
}

在这个实现中，我们首先检查堆的大小是否为0，如果为0则说明堆为空，返回-1表示失败。否则，将堆顶元素替换为最后一个元素，同时将堆大小减1。接着进行下沉操作将堆顶元素调整到正确的位置，最后返回原来的堆顶元素。

以上就是C++实现小顶堆的一个简单示例。在实际应用中，还可以基于这个实现进行扩展，新增更多的操作方法以及对其他元素类型的支持等。

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

下一篇: C++中的!x是什么意思？

评论区

()

相似文章