使用 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) 时间运行。因此，每种方式的运行时间为：

• 答：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 个项目进行 4 次交换。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而且速度要快得多。