证明二进制堆构建最大比较是(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次.

由于累积堆要求你换一个项目以最小的孩子,它需要两个比较发起交换:一个寻找最小的两个孩子,和一个以确定该节点是更大的,必须被交换.

移动节点所需的比较次数是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个级别(大小一百万并且更改),并且它是成立的:N个项目的完整堆移动的最大级别数是N-log2(N + 1).

将上述系列作为Arithetico几何序列,我们计算项的和log2(N + 1) - 1,忽略第一项,因为它是零,等于N - 1.(回想一下完整的二叉树有log2(N + 1)水平)

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