Heaps
优质
小牛编辑
125浏览
2023-12-01
堆是一种特殊的树结构,其中每个父节点小于或等于其子节点。 然后它被称为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]