Heaps

堆是一种特殊的树结构，其中每个父节点小于或等于其子节点。 然后它被称为Min Heap。 如果每个父节点大于或等于其子节点，则称其为最大堆。 实现优先级队列是非常有用的，其中具有较高权重的队列项在处理中被赋予更多优先级。 有关堆的详细讨论，请访问我们的网站。 如果您不熟悉数据结构，请先学习它。 在本章中，我们将看到使用python实现堆数据结构。

创建一个堆

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

• heapify - 此函数将常规列表转换为堆。 在生成的堆中，最小的元素被推送到索引位置0.但是其余的数据元素不一定要排序。
• heappush - 此函数在不更改当前堆的情况下向堆中添加元素。
• heappop - 此函数返回堆中的最小数据元素。
• heapreplace - 此函数使用函数中提供的新值替换最小的数据元素。

创建堆

只需使用具有heapify函数的元素列表即可创建堆。 在下面的例子中，我们提供了一个元素列表，而heapify函数重新排列了将最小元素带到第一个位置的元素。

import heapq
H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
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]
# Create the heap
heapq.heapify(H)
print(H)
# Remove element from the heap
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]
# Create the heap
heapq.heapify(H)
print(H)
# Replace an element
heapq.heapreplace(H,6)
print(H)

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