Python 堆队列算法

---

堆数据结构可以用来表示优先队列。在 Python 中，它可以通过 heapq 模块使用。这里它创建了一个最小堆。因此，当优先级为 1 时，它表示最高优先级。当插入新元素时，堆结构会更新。

要使用此模块，我们应该使用以下方法导入它：

import heapq

有一些与堆相关的操作。它们是：

方法 heapq.heapify(iterable)

它用于将可迭代数据集转换为堆数据结构。

方法 heapq.heappush(heap, element)

此方法用于将元素插入堆中。之后重新堆化整个堆结构。

方法 heapq.heappop(heap)

此方法用于返回并从堆顶删除元素，并在其余元素上执行堆化。

方法 heapq.heappushpop(heap, element)

此方法用于在一个语句中插入和弹出元素。

方法 heapq.heapreplace(heap, element)

此方法用于在一个语句中插入和弹出元素。它从堆的根部删除元素，然后将元素插入堆中。

方法 heapq.nlargest(n, iterable, key=None)

此方法用于从堆中返回 n 个最大元素。

方法 heapq.nsmallest(n, iterable, key=None)

此方法用于从堆中返回 n 个最小元素。

示例代码

在线演示

import heapq
my_list = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
heapq.heapify(my_list)
print(my_list)
heapq.heappush(my_list, 7)
print(my_list)
print('Popped Element: ' + str(heapq.heappop(my_list)))
print(my_list)
new_iter = list()
new_iter = heapq.nlargest(4, my_list)
print(new_iter)

输出

[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19]
Popped Element: 7
[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[89, 65, 58, 41]