Python 堆
Python 堆详细操作教程
堆是一种特殊的树结构，其中每个父节点均小于或等于其子节点。这就是所谓的Min Heap。如果每个父节点大于或等于其子节点，则称为最大堆。实施优先级队列非常有用，在该队列中，权重较高的队列项目在处理中具有更高的优先级。有关堆的详细讨论，请参见我们的网站。如果您不熟悉数据结构，请先进行研究。在本章中，我们将看到使用python实现堆数据结构的方法。
创建一个堆
堆是使用python内置的名为heapq的库创建的。该库具有相关的功能，可以对堆数据结构执行各种操作。下面是这些功能的列表。
heapify-此函数将常规列表转换为堆。在结果堆中，最小的元素被推到索引位置0。但是其余数据元素不一定要排序。
heappush –此函数在不更改当前堆的情况下将元素添加到堆中。
heappop-此函数返回堆中最小的数据元素。
heapreplace –该函数用函数中提供的新值替换最小的数据元素。
创建堆
堆是通过简单地使用带有heapify函数的元素列表来创建的。在下面的示例中，我们提供了元素列表，并且heapify函数重新排列了元素，将最小的元素移到了第一个位置。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
import heapq
H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)
运行结果如下：
插入堆
向堆中插入数据元素总是将元素添加到最后一个索引。但是您可以再次应用heapify函数，以将新添加的元素的值最小时才将其添加到第一个索引。在下面的示例中，我们插入数字8。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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的元素。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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]
更换堆
heapreplace函数始终会删除堆中最小的元素，并将新的传入元素插入未按任何顺序固定的某个位置。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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]
