Python - 堆(Heaps)

堆(Heaps)是一种特殊的树结构，其中每个父节点均小于或等于其子节点，这就是所谓的最小堆，如果每个父节点大于或等于其子节点，则称为最大堆。

堆是使用python内置的名为heapq的库创建的，该库具有相关的功能，可以对堆数据结构执行各种操作。下面是这些功能的列表。

• heapify         - 此函数将常规列表转换为堆。
• heappush     -  此函数在不更改当前堆的情况下向堆中添加了一个元素。
• heappop       - 此函数返回堆中最小的数据元素。
• heapreplace - 此函数用函数中提供的新值替换最小的数据元素。

创建堆

堆是通过简单地使用带有heapify函数的元素列表来创建的，在下面的示例中，提供了元素列表，并且heapify函数重新排列了元素，将最小的元素移到了第一个位置。

import heapq

H=[21,1,45,78,3,5]
#使用 heapify 重新排列元素
heapq.heapify(H)
print(H)

执行以上代码后，将产生以下输出-

[1, 3, 5, 78, 21, 45]
 

插入堆

将数据元素插入堆中总是将元素添加到最后一个索引，但是您可以再次应用heapify函数，以将新添加的元素的值最小时才将其添加到第一个索引。在下面的示例中插入数字8。

import heapq
H=[21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

执行以上代码后，将产生以下输出-

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]
 

从堆中删除

您可以使用此功能删除第一个索引处的元素，在下面的示例中，该函数将始终删除索引位置为1的元素。

import heapq

H=[21,1,45,78,3,5]
# 创建堆

heapq.heapify(H)
print(H)

# 从堆中移除元素
heapq.heappop(H)

print(H)

执行以上代码后，将产生以下输出-

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]
 

更换堆元素

heapreplace函数始终会删除堆中最小的元素，并将新的传入元素插入未按任何顺序固定的某个位置。

import heapq

H=[21,1,45,78,3,5]
# 创建堆

heapq.heapify(H)
print(H)

# 替换元素
heapq.heapreplace(H,6)
print(H)

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]