Python数据结构教程：堆（特殊树结构）

堆是一种特殊的树结构，其中每个父节点都小于或等于其子节点。那么它被称为最小堆（Min Heap）。如果每个父节点都大于或等于其子节点，则称为最大堆（Max 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]

替换堆

堆函数总是固定其中最小的元素在其中插入新传入元素的位置。看下面的例子 -

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]