heapq模块的使用方法

Question

我不明白如何正确使用 heapq 模块。

我意识到，无需将我的列表转换为堆（不使用 heapify），我仍然可以使用其他需要堆作为输入的函数（heappop、heappush..）。那么什么时候需要使用heapify呢？

我是否应该创建一个空列表，使用 heapify 将其转换为堆，然后再使用它？我试过了。我得到了 TypeError。

my_list = heapq.heapify([0])
heapq.heappush(my_list, -8)    
TypeError: heap argument must be a list
        heapq.heappush(my_list, -8)

在下面的示例中，如果我不将我的列表转换为堆，我可以使用 heappush 将 -8 推送到我的列表。但是，当我想查看堆的最小元素时，它给了我 0。在 heapq 文档中，它说我可以使用索引 0 到达最小元素。

my_list = [0]
heapq.heappush(my_list, -8)
print(my_list, my_list[0])

output: [0, -8] 0

我试图在循环中使用它，所以我希望能够执行快速的推送和弹出操作，而无需在每次迭代中将列表转换为堆，这将花费 O(N)

Answer 1

当您不是从空列表开始并且要将列表转换为堆时，您应该使用 heapify inplace.

>>> queue = [1,9,2,4]
>>> heapify(queue)
>>> queue
[1, 4, 2, 9]

当你从一个空列表开始时，那么你可以直接在列表上进行heappush、heappop、heappushpop等操作。
示例：

>>> queue = []
>>> heappush(queue, 3)
>>> heappush(queue, 1)
>>> heappush(queue, 4)
>>> heappop(queue)
1
>>> heappop(queue)
3
>>> heappop(queue)
4

你得到一个错误，因为你正在使用 heapify 的 return 值，它是 None 因为它是原位的。

>>> res = heapify([1,9,2,4])
>>> res is None
True

How to use heapq module