python - heapify 和 heappush 有什么区别？哪个更好？

Question

heapify 和 heapush 都将最小的项目放在顶部，最低的项目位于正确的位置。我不明白有什么区别和用法差异

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap

# Add element
heapq.heappush(H,-100)
heapq.heappush(H,-98)
heapq.heappush(H,-1)
print(H)
heapq.heapify(H)

print(H)


# output: [-100, -98, 21, -1, 3, 5, 45, 78, 1]
# [-100, -98, 5, -1, 3, 21, 45, 78, 1]

Answer 1

heappush 和 heapify 之间存在多个差异。

1. heappush 假设数组(在您的情况下为 H)已经是一个堆。 heapify 不需要——H 只需是一个列表。请注意，在您的示例中，在执行三个 heappush 命令之前，您的数据结构 H 不是堆。 (例如，H 开头为 [21,1,45,78,3,5]，但第一项 21 大于第二项 1，这违反了堆的定义。)因此，在 heappush 命令之后，H 也不是堆。 (H 变为 [-100, -98, 21, -1, 3, 5, 45, 78, 1] 但第三项 21大于第6项5，这也违反了堆的定义。)在heapify之后，5和 21 项交换了位置，然后 H 就是一个正确的堆。
2. heappush 向堆添加一个新值。 heapify 不会添加值 - 它会重新排列列表中的值。
3. 您可以通过创建一个空堆，然后为要添加的每个项目调用 heappush 来构建堆，或者您可以按任意顺序创建项目列表，然后调用 heapify 就行了。 heappush 方法的时间复杂度为 O(n * log(n))，其中 n 是堆的结束大小，而 heapify 方法复杂度为 O(n)，显着降低。例如，如果您要创建一个包含一百万个项目的堆，则 heappush 方法最多可以使用 20,000,000 次操作，而 heapify code> 方法最多仅使用 1,000,000 次操作。这是 20 的差异。当然，操作并不完全相同，实际数字略有不同，因此实际因素会有所不同，但 heapify 几乎肯定会更快。
4. 构建堆的 heappush 方法需要许多单独的语句或某种循环来添加项目。 heapify 方法只需要列表存在。因此，heapify 方法很可能会使用更少的代码行和更少的代码复杂性。 (在代码中添加 for 循环会增加另一层复杂性，从而导致更多错误。)

总之，在列表上执行 heapify 几乎总是比创建空列表并使用 heappush 添加许多项目更好的选择。如果您只添加一些项目，heappush 可能会更好。