为什么使用 heapq.heapify 创建的堆与迭代 heapq.heappush 创建的堆不同

Question

我注意到给定一个列表，如果我使用 heapq.heapify() 创建一个堆，元素的顺序与我迭代列表并执行 heap.heappush 时获得的顺序不同().

有人可以帮我理解为什么吗？

此外，给定可迭代对象，创建堆的一种方法是否比另一种方法更好，为什么？

Answer 1

I noticed that given a list, if i create a heap using heapq.heapify(), the elements are in a different order than what I obtain if i iterate over the list and do heap.heappush().

Could someone help me understand why?

没有理由它们应该相同。存储数据的方式不止一种。

Also, given the iterable, is one way better than the other for creating a heap and why?

做一个列表交给heapify（这就是heapify的作用，它更简单，而且它也有更好的渐近性能，如果重要的话。）

Answer 2

heapify使用了一个O(n)的算法，区别于单纯的一个一个插入，只需要O(n log n)。查看其中 Wikipedia's description 个。