Python 中的最小堆实现

最小堆是一种数据结构，它满足堆属性，即每个节点的值都小于或等于其子节点的值。这意味着堆的最小值始终存储在根节点。

以下是构建最小堆的算法：

1. 创建一个空的列表来表示堆。
2. 对于输入列表中的每个元素，使用insert 函数（如下所述）将其插入堆中。
3. 返回堆。

insert 函数接收一个堆和一个值，并将该值添加到堆中，同时保持堆属性。

insert 函数的算法：

1. 将新值添加到堆的末尾。
2. 当值不在堆的根节点且其父节点大于该值时
3. 交换该值与其父节点。
4. 更新该值及其父节点的索引。
5. 返回更新后的堆。

示例

实现此算法的 Python 程序

输出

[1, 3, 5, 4, 8, 7]

build_heap 方法首先将输入列表复制到heap数组中，然后对堆中的每个非叶节点调用min_heapify方法，从底部开始向上构建。它确保生成的堆满足最小堆属性。

• __init__: 此方法仅初始化一个空列表来存储堆。其时间复杂度为O(1)，其空间复杂度为O(1)。
• parent, left_child, and right_child: 这些方法仅计算给定节点的父节点和子节点的索引。它们的时间复杂度为O(1)，其空间复杂度为O(1)。
• insert: 此方法将一个值插入堆中，并通过根据需要与其父节点交换新值来恢复最小堆属性。在最坏的情况下，新值可能需要一直交换到树的根节点，这需要O(log n)。因此，insert 的时间复杂度为O(log n)，其空间复杂度为O(1)。
• get_min: 此方法返回堆中的最小值，该值始终是树的根。其时间复杂度为O(1)，其空间复杂度为O(1)。
• extract_min: 此方法从堆中删除最小值，并通过将堆中的最后一个元素与根交换，然后根据需要将根与其较小的子节点交换来恢复最小堆属性。在最坏的情况下，新根节点可能需要一直交换到树的叶节点，这需要O(log n)。因此，extract_min的时间复杂度为O(log n)，其空间复杂度为O(1)。
• build_heap: 此方法通过对堆中的每个非叶节点调用min_heapify来从输入列表构建最小堆。每次调用 min_heapify 需要O(log n)时间，堆中有O(n)个非叶节点，因此 build_heap 的总时间复杂度为O(n log n)。其空间复杂度为O(n)，因为它需要将输入列表复制到堆数组中。
• min_heapify:此方法通过根据需要与最小子节点交换节点来恢复节点及其子节点的最小堆属性。在最坏的情况下，节点可能需要一直交换到树的叶节点，这需要O(log n)。因此，min_heapify 的时间复杂度为O(log n)，其空间复杂度为O(1)。
• __len__:此方法返回堆中的元素数量，即堆列表的长度。其时间复杂度为O(1)，其空间复杂度为O(1)。

总而言之，MinHeap 类的构建堆的最坏情况时间复杂度为O(n log n)，插入、提取和最小堆化操作为O(log n)。其最坏情况空间复杂度为O(n)，因为在构建堆时需要将输入列表复制到堆数组中。

一种替代方法是使用表示为二叉树的二叉堆，其中每个节点最多有两个子节点。在此表示中，堆存储在列表中，其中索引 i 处节点的父节点位于索引 (i-1)//2 处，而索引 i 处节点的左和右子节点分别位于索引 2*i+1 和2*i+2 处。

示例

输出

[1, 3, 5, 4, 8, 7]

说明

在此实现中，__init__方法接受一个可选的lst参数，如果提供了该参数，则用于构建堆。build_heap方法接受一个列表作为输入，并就地修改堆以确保它满足最小堆属性。

这两种方法基本相同。在这两种情况下，我们都使用数组实现了二叉最小堆来存储堆，并且我们使用min_heapify方法来确保在每次插入或删除操作后都满足最小堆属性。

这两种实现之间的唯一区别是，在第一种方法中，build_heap方法接受一个列表作为输入并从头创建一个新的堆，而在第二种方法中，build_heap方法修改一个已存在的表示为数组的堆。