什么是Python中的Heap队列（或heapq）？

Heap队列是一种特殊的树形结构，其中每个父节点都小于或等于其子节点。在Python中，它使用heapq模块实现。它非常有用用于实现优先队列，在处理中给具有更高权重的队列项更高的优先级。

更多Python相关文章，请阅读：Python 教程

创建堆

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

• heapify – 该函数将常规列表转换为堆。在生成的堆中，最小元素被推送到索引位置0。但是，其余的数据元素不一定排
• heappush – 该函数添加一个元素到队列而不改变当前堆。
• heappop – 该函数从队列中返回最小的数据元素。
• heapreplace – 该函数将最小数据元素替换为函数中提供的新值。

创建堆

堆通过简单地使用元素列表和heapify函数来创建。在下面的示例中，我们提供了一个元素列表，heapify函数将重新排列元素，并将最小元素带到第一个位置。

示例

import heapq

H = [21,1,45,78,3,5]
# 使用heapify来重新排列元素
heapq.heapify(H)
print（H）

输出

当执行上述代码时，它将生成以下结果 –

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

插入堆中

将数据元素插入堆总是将其添加到最后一个索引位置。但是，如果堆中新添加的元素最小，则可以再次应用heapify函数将其带到第一个索引位置。在下面的示例中，我们插入数字8。

示例

import heapq
H = [21,1,45,78,3,5]
# 将其转换为堆
heapq.heapify(H)
print（H）
# 添加元素
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]
# 创建堆
heapq.heapify(H)
print（H）

# 从堆中删除元素
heapq.heappop(H)

print（H）

输出

当执行上述代码时，它将生成以下结果 –

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

替换堆中的元素

heapreplace函数始终删除堆的最小元素，并将新的传入元素插入未固定的位置。

示例

import heapq

H = [21,1,45,78,3,5]
# 创建堆

heapq.heapify(H)
print（H）

# 替换元素
heapq.heapreplace(H,6)
print（H）

输出

当执行上述代码时，它将生成以下结果 –

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