python - 带有常规列表的 Heapop 和 Heappush（非堆化列表）

Question

因此，我看到了各种帖子，其中用户在尝试从常规列表中进行堆放时会得到“不寻常/意外”的结果。(ex: Unusual result from heappop? ) 解决办法当然是先堆化它。

然而，对于这个LeetCode 解决方案， heapq 方法用于一个常规列表，该列表在使用这些方法之前没有被堆化，但仍然返回正确的预期结果。这是因为当您在常规列表中使用 heappop/heappush 时，它只会弹出/添加列表中的第一个元素？

标签： pythonheapq

Answer 1

在示例中，他们在最初包含单个元素（源）的列表上使用heappop ，因此它满足 heap 属性。在使用或等函数之前
，不必heapify在列表中使用。实际上，列表可能是空的，包含单个元素，或者是已经满足堆属性的列表。heappopheappush

例子：

>>> l = [1, 3, 2, 5, 4] # initial list that respects the heap property
>>> heappop(l)
1
>>> heappop(l)
2
>>> heappop(l)
3
>>> heappop(l)
4
>>> heappop(l)
5