对 heapify 进行更严格的绑定

Question

我想使用 siftdown 方法计算 heapify 上更严格的界限，因此我按如下方式进行：

在每个级别 i 上，该级别上的每个键都可以转到叶级别 h （其中h 是树的高度）在最坏的情况下。
由于第 i 层有 2ⁱ 个节点，因此完成的总工作为

Σ_0≤i≤h (h - i ) * 2ⁱ

但我无法继续下去。我知道它必须达到 O(n) 但我无法达到它。请帮我解决这个问题。

Answer 1

S = Σ_0≤i≤h (h - i ) * 2ⁱ

S = h + 2(h - 1) + 4(h - 2) + .. . + 2^{h - 1} ... (1)

两边都乘以 2，2S

= 2h + 4(h - 1) + 8(h - 2) + ... + 2^h ... (2)

从 (2) 中减去 (1)，

S = h -2h + 2 + 4 + 8 + …。 + 2^h

= -h – 1 + (1 + 2 + 4 + 8 +… + 2^h )

= (2^{h + 1} - 1) – (h + 1)

[注：1 + 2 + 4 + 8 + ... + 2^h = (2^{h + 1} - 1)

由于高度为 h 的完全二叉树具有 2h 到 2h + 1 个节点，因此上述总和为 O(n)，其中 n 是堆中的节点数。

Answer 2

如果您不是从顶部开始计数，而是从底部开始计数，那么会更容易看出。因此，如果我们说 i 是距底部的高度，我们会将总和转换为：

Σ i * 2^hi

= 2^h * Σ i / 2ⁱ

= 2^h * O(1)

= O(2^logn) = O(n)

我用 logn 交换了 h ，因为这是一个二进制文件堆。

我将证明为什么该和是 O(1)：

该和是 i/2ⁱ 项的有限和，因此如果我们显示无限和的收敛性 (i-->infinite ）那么显然每个有限和（即对于所有n）将小于该值（因为所有项都是正数）。这意味着每个有限和都受一个常数限制，即 O(1)。

我们只剩下无限 Σ i / 2ⁱ 收敛的证明。我们可以使用无数的收敛测试，让我们使用 Σ 1 / i² 收敛的简单结果，并表明对于足够大的 i ，这将是我们总和的上限：

我们想要证明，对于足够大的情况i:

i/2^{i 1/i2}

发生当且仅当 i³ < 2ⁱ 这对于 i > 来说是正确的。 10

量子电动力学