Python - 堆

---

---

堆是一种特殊的树形结构，其中每个父节点都小于或等于其子节点。如果是这样，则称为最小堆。如果每个父节点都大于或等于其子节点，则称为最大堆。它在实现优先队列方面非常有用，在优先队列中，权重较高的队列项在处理中具有更高的优先级。

关于堆的详细讨论可在我们的网站上找到。如果您不熟悉堆数据结构，请先学习它。在本节中，我们将学习使用 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)

输出

执行上述代码后，将产生以下结果：

[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]