Python - 堆数据结构

---

---

堆是一种特殊的树结构，其中每个父节点都小于或等于其子节点。那么它被称为 Min Heap。如果每个父节点都大于或等于其子节点，则称为最大堆。实施优先级队列非常有用，其中权重较高的队列项目在处理中被赋予更高的优先级。

如果您不熟悉堆数据结构，请先学习它。在本章中，我们将看到使用 python 实现堆数据结构。

创建堆

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

• 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)

输出

执行上述代码时，它会产生以下结果 -

插入堆

将数据元素插入堆始终会在最后一个索引处添加该元素。但是，只有当新添加的元素值最小时，你才能再次应用 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)

输出

执行上述代码时，它会产生以下结果 -

从堆中删除

您可以使用此函数删除 First Index 处的元素。在下面的示例中，该函数将始终删除索引位置 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)

输出

执行上述代码时，它会产生以下结果 -

在堆中替换

heap replace 函数总是删除堆的最小元素，并将新的传入元素插入到任何顺序都未固定的位置。

例

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)

输出

执行上述代码时，它会产生以下结果 -