如何在 C++ 中实现最小堆

当我们需要一种数据结构来处理**插入、删除**和**查找**最小元素，并且时间复杂度为 **O(Logn)** 时，最小堆就派上用场了。在本文中，我们将探讨如何在 C++ 中实现最小堆。一个完整的二叉树，可以是最小堆或最大堆，被称为**二叉堆**。**最大二叉堆**的根键必须是堆中所有其他键中最大的。对于**二叉树**中的每个节点，此属性都需要递归地成立。最小堆与**最小二叉堆**类似。

最小堆算法

对于 min_heap()

示例

我们以一个例子来说明如何在 C++ 中实现**最小堆**

输出

Enter the number of elements in the array: 10
Enter 10 elements: 25 10 30 5 15 40 20 35 45 50
Min Heap:
5 10 20 25 15 40 30 35 45 50

最小堆的 C++ 表示

最小堆存储在一个数组中。根元素是 **Arr[0]**。

对于索引为 i 的节点

重要的 MinHeap 方法

insert()

新元素**插入**到堆数组的末尾。之后，通过将其当前元素与其父元素交换来恢复堆属性，直到父元素的值超过当前值。将元素插入**最小堆**需要 **O(Logn)** 的时间。

getMin()

它提供根元素（最小元素）的值。**MinHeap** 中的 **getMin** 的时间复杂度为 **O(1)**。

extractMin()

此过程删除并返回**最小堆**的根元素。在将堆的最后一个元素与根元素交换之后，**最小堆**将执行**堆化**过程。**ExtractMin()** 的时间复杂度为 **O(Logn)**。

decreaseKey()

使用此技术时，**索引 i** 处的键值会减小。此方法的时间复杂度为 **O(Logn)**。

delete()

此过程用于删除**索引 i** 处的键。**最小堆**的删除操作的时间复杂度为 **O(Logn)**。

二叉堆的特点

以下是二叉堆的特点

它是一个完全二叉树。换句话说，所有层都完全填满。即使最后一层可能没有完全完成，其所有组成部分都在**左侧**。这个特性使得二叉堆可以存储在**一维数组**中。

二叉堆有两种类型：**最小堆**和**最大堆**。在**最小/最大堆**中，根元素的值是最小的或最大的。

结论

本文介绍了最小堆的 C++ 实现。还探讨了最小堆的一些最关键的技术。