0

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

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

我应该创建一个空列表，使用 heapify 将其转换为堆，然后使用它吗？我试过这个。我得到了类型错误。

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)

4

1 回答 1

2

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

>>> 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 的返回值，因为它是就地的，所以它是 None 。

>>> res = heapify([1,9,2,4])
>>> res is None
True
于 2021-01-03T20:50:08.370 回答