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]