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 之间存在多个差异。

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

总而言之，对列表进行 heapify 几乎总是比创建一个空列表并使用 heappush 添加许多项目更好的选择。如果只是添加几个项目，heappush 可能会更好。

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

What is the difference in heapify and heappush? which is better?

python

heap