python - 使用 heapify 与 heappush 创建堆。哪个更快？

Question

问题

我必须创建一个优先级队列来存储距离。为了构建堆，我正在考虑以下两种可能性:

from heapq import heapify, heappush
n = 35000  # input size

# way A: using heapify
dist = []
for i in range(n):
  dist.push(distance)  # distance is computed in O(1) time
heapify(dist)

# way B: using heappush
dist = []
for i in range(n):
  heappush(dist, distance)  # distance is computed in O(1) time

哪个更快？

推理

根据文档，heapify() 以线性时间运行，我猜 heappush() 以 O(log n) 时间运行。因此，每种方式的运行时间为:

• A: O(2n) = O(n)
• B: O(n log n)

但是，A 比 B 快对我来说是违反直觉的。我是不是漏掉了什么？ A真的比B快吗？

**编辑

我一直在测试不同的输入和不同大小的数组，但我仍然不确定哪个更快。

在阅读了 Elisha 的评论链接后，我明白了 heapify() 是如何在线性时间内运行的。但是，我仍然不知道使用 heappush() 是否会更快，具体取决于输入。

我的意思是，heappush() 的最坏情况 运行时间为 O(log n)，但平均而言可能更短，具体取决于输入。它的最佳情况运行时间实际上是 O(1)。另一方面，heapify() 的最佳情况 运行时间为 O(n)，并且必须在填充数组后调用，这也需要 O(n)。这是 O(2n) 的最佳情况。

因此 heappush() 可能与线性一样快或与 O(n log n) 一样慢，而 heapify() 将花费 2n 任何情况下的时间。如果我们看最坏的情况，heapify() 会更好。但是一般情况呢？

我们甚至可以确定其中一个比另一个更快吗？

Answer 1

是的，我们可以确定一个比另一个快。

heap.push 从下往上构建堆。每个项目都被添加到数组的末尾，然后“冒泡”到它的正确位置。如果您正在构建一个最小堆并且您以相反的顺序显示项目，那么您插入的每个项目都需要进行 log(n)(n 是堆的当前大小)比较。所以通过插入建堆的最坏情况是O(n log n)。

想象一下，从一个空堆开始，并以相反的顺序添加 127 个项目(即 127、126、125、124 等)。每个新项目都小于所有其他项目，因此每个项目都需要最大数量的交换才能从最后一个位置冒泡到顶部。添加的第一个项目进行零交换。接下来的两个项目各进行一次交换。接下来的四个项目每个进行两次交换。八个项目进行三个交换。 16 个项目进行四次交换。 32 项进行 5 次交换，64 项进行 6 次交换。计算结果为:

0 + 2*1 + 4*2 + 8*3 + 16*4 + 32*5 + 64*6
0 + 2 + 8 + 24 + 64 + 160 + 384 = 642 swaps

build-heap 的最坏情况是 n 次交换。考虑同样包含 127 个项目的数组。叶级包含 64 个节点。 build-heap 从中间点开始，向后移动，根据需要向下移动。倒数第二层有 32 个节点，最坏情况下它们会下移一层。上一层有 16 个节点，不能向下移动超过两层。如果你把它加起来，你会得到:

64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6
0 + 32 + 32 + 24 + 16 + 10 + 6 = 120 swaps

这绝对是 build-heap 的最坏情况。是 O(n)。

如果您在一个包含一百万个项目的数组上分析这两种算法，您会发现运行时间存在巨大差异，build-heap 要快得多。