在Python3中初始化堆后是否需要进行heapify

Question

当创建堆来动态跟踪最小值时，在初始化空堆后，我实际上需要调用吗heapq.heapify(heap)？或者更确切地说hq.heappop()，它将hp.heappush()自动完成这项工作..感谢您的帮助！

import heapq as hp
heap = []
hp.heapify(heap) # is this line redundant?
for val in range(1, 100):
    hp.heappush(heap, val)
    print(heap[0])

Answer 1

是的，就你而言，这是多余的。来自官方文档：

heapq.heappush（堆，项目）

将值项推入堆，保持堆不变。

heapq.heapify(x)

在线性时间内将列表 x 就地转换为堆。

从该方法的描述中可以看出heapify，它用于将现有列表转换为堆结构。

但是，如果您想在添加新元素时保留数据结构的堆属性，那么这heappush是一种方法。

import heapq as hp
heap = []
for val in range(1, 100):
    hp.heappush(heap, val)
    print(heap[0])

但是，如果您想将现有数组/列表转换为堆，请使用以下heapify方法：

import heapq as hp
heap = []
for val in range(1, 100):
    heap.append(val)
hp.heapify(heap)
print(heap[0])