algorithm - 在 heapify 上绑定(bind)更紧

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 – 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 是堆中的节点数。