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

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

是的，在您的情况下这是多余的。来自官方文档 here:

heapq.heappush(heap, item)

Push the value item onto the heap, maintaining the heap invariant.

heapq.heapify(x)

Transform list x into a heap, in-place, in linear time.

从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])

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

Do I need to heapify after initializing a heap in Python3

python-3.x

heap

min-heap