algorithm - 证明二叉堆构建最大比较是 (2N-2)

Question

我试图证明对于二叉堆，buildHeap 最多在元素之间进行 (2N-2) 次比较。 我发现很难证明这一说法。

Answer 1

构建堆算法从中点开始，并根据需要向下移动项目。让我们考虑一堆 127 个项目(7 个级别)。在最坏的情况下:

64 nodes (the leaf level) don't move at all
32 nodes move down one level
16 nodes move down two levels
 8 nodes move down three levels
 4 nodes move down four levels
 2 nodes move down five levels
 1 node moves down six levels

所以在最坏的情况下你有

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

所以在最坏的情况下，构建堆进行的交换少于 N 次。

因为 build-heap 要求你交换一个项目与其最小的 child ，它需要两次比较来启动交换:一个是找到两个 child 中最小的，另一个是确定节点是否更大并且必须被交换。

移动一个节点所需的比较次数为2*(levels_moved+1)，并且不会移动超过N/2个节点。

一般情况

我们需要证明最大比较次数不超过2N-2。正如我上面提到的，需要两次比较才能将节点移动一级。所以如果移动的层数小于N(即(N-1)或更少)，那么最大比较次数不能超过2N-2。

我在下面的讨论中使用了一个完整的堆，因为它代表了最坏的情况。

在 N 个项目的完整堆中，叶级有 (N+1)/2 个节点。 (N+1)/4 在下一层。 (N+1)/8 在下一个，等等。你最终得到这个:

(N+1)/2 nodes move 0 levels
(N+1)/4 nodes move 1 level
(N+1)/8 nodes move 2 levels
(N+1)/16 nodes move 3 levels
(N+1)/32 nodes move 4 levels
...

这给了我们系列:

((N+1)/2)*0 + ((N+1)/4)*1 + ((N+1)/8)*2 + ((N+1)/16)*3 ...

让我们看看它对不同大小的堆做了什么:

heap size  levels   levels moved
   1         1          0
   3         2          1
   7         3          2*1 + 1*2 = 4
   15        4          4*1 + 2*2 + 1*3 = 11
   31        5          8*1 + 4*2 + 2*3 + 1*4 = 26
   63        6          16*1 + 8*2 + 4*3 + 2*4 + 1*5 = 57
   127       7          32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120
         ....

我对最多 20 层的堆(大小为 100 万，并且有变化)运行了该方法，结果成立:对于 N 项的完整堆，移动的最大层数是 N-log2(N+1)。

将以上系列作为Arithetico-geometric Sequence ，我们计算 log2(N + 1) - 1 项的总和，忽略第一项，因为它为零，等于 N - 1。 (回想一下，完整的二叉树有 log2(N + 1) 层)

此总和表示执行 siftup 操作的总次数。因此所需的比较总数为 2N - 2(因为每次筛选操作需要两次比较)。这也是上限，因为完整的二叉树总是代表给定树深度的最坏情况。