Python Data Structure 简明教程

Python - Heaps

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

关于堆的详细讨论可在我们的网站上获得这里。如果你不熟悉堆数据结构，请先学习它。在本章中，我们将看到使用 Python 实现堆数据结构。

Create a Heap

通过使用名为 heapq 的 Python 内置库来创建堆。此库具有执行堆数据结构上各种操作的相关函数。以下是这些函数的列表。

  1. heapify − 此函数将常规列表转换为堆。在结果堆中，最小的元素会被推送到索引位置 0。但其他数据元素不一定按顺序排列。

  2. heappush − 此函数将元素添加到堆中，而不会改变当前的堆。

  3. heappop − 此函数从堆中返回最小的数据元素。

  4. heapreplace − 此函数用函数中提供的新值替换最小的数据元素。

Creating a Heap

只需使用带堆化函数的元素列表就可以创建堆。以下示例中，我们提供一个元素列表，堆化函数重新排列元素，将最小元素放置在第一位。

Example

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Output

执行上述代码后，将生成以下结果 −

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

Inserting into heap

向堆中插入数据元素时总是将元素添加到最后一个索引位置。但只在该元素的数值最小的情况下，才能再次应用堆化函数以将新添加的元素移动到第一索引位置。以下示例中，我们插入数字 8。

Example

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)

Output

执行上述代码后，将生成以下结果 −

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

Removing from heap

可以使用此函数移除第一个索引位置处的元素。以下示例中，该函数总是将索引位置为 1 处的元素移除。

Example

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)

Output

执行上述代码后，将生成以下结果 −

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

Replacing in a Heap

堆替换函数始终移除堆中最小的元素，并将新进入的元素插入某个未按任何顺序固定的位置。

Example

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)

Output

执行上述代码后，将生成以下结果 −

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