证明二进制堆构建最大比较为（2N-2） [英] prove that binary heap build max comparsion is (2N-2)

问题描述

我试图证明对于二进制堆，buildHeap最多进行元素之间的（2N-2）比较。
我很难证明这一主张。

解决方案

build-heap算法从中点开始并移动项目按要求减少。让我们考虑一堆127个项目（7个级别）。在最坏的情况下：

  64个节点（叶级）根本不移动
 32个节点向下移动一级
 16个节点下移两个级别
 8个节点下移三个级别
 4个节点下移四个级别
 2个节点下移五个级别
 1个节点下移六个级别
  

所以在最坏的情况下，您有

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

因此，在最坏的情况下，构建堆的数量少于N个掉期。

因为构建堆要求您以最小的子项交换项目，所以需要进行两次比较以启动交换：一次是找到最小项

移动一个节点所需的比较次数为 2 *（levels_moved + 1），最多只能移动N / 2个节点。

一般情况

我们需要证明比较的最大次数不超过2N-2。如上所述，将节点移动到一个级别需要进行两次比较。因此，如果移动的级别数小于N（即（N-1）或更少），则最大比较数不能超过2N-2。

I在下面的讨论中使用满堆，因为它代表最坏的情况。

在满N个项目的堆中，（N + 1）/ 2个节点叶水平。 （N + 1）/ 4在下一级。 （N + 1）/ 8在下一个，以此类推。

 （N + 1）/ 2节点移动0个级别
（N + 1）/ 4个节点移动1个级别
（N + 1）/ 8个节点移动2个级别
（N + 1）/ 16个节点移动3个级别
（N + 1）/ 32个节点移动4个级别
 ... 
  

那给了我们一系列：

 （（N + 1）/ 2）* 0 +（（N + 1）/ 4 ）* 1 +（（（N + 1）/ 8）* 2 +（（N + 1）/ 16）* 3 ... 
  

让我们看看不同大小的堆的作用：

 堆大小级别移动了
 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 
 .... 
   
 
 
采用上述系列作为算术几何序列，我们计算 log2（N +1）-1 个词，忽略第一个项，因为它为零，等于 N-1 。 （回想一下，完整的二叉树具有 log2（N +1）个级别）
 
 
 
此总和表示总数进行筛分操作的次数。因此所需的比较总数为 2N-2 （因为每个筛选操作都需要进行两次比较）。这也是上限，因为对于给定的树深度，完整的二叉树总是代表最坏的情况。
 
I am trying to prove that for binary heaps, buildHeap does at most (2N-2) comparisons between elements.
I find it very difficult to prove this claim.
解决方案
The build-heap algorithm starts at the midpoint and moves items down as required. Let's consider a heap of 127 items (7 levels). In the worst case:
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
So in the worst case you have
64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6
0 + 32 + 32 + 24 + 16 + 10 + 6 = 120 swaps
So in the worst case, build-heap makes fewer than N swaps.

Because build-heap requires that you swap an item with the smallest of its children, it requires two comparisons to initiate a swap: one to find the smallest of the two children, and one to determine if the node is larger and must be swapped.

The number of comparisons required to move a node is 2*(levels_moved+1), and no more than N/2 nodes will be moved.

The general case

We need to prove that the maximum number of comparisons is no more than 2N-2. As I noted above, it takes two comparisons to move a node one level. So if the number of levels moved is less than N (i.e. (N-1) or fewer), then the maximum number of comparisons cannot exceed 2N-2.

I use a full heap in the discussion below because it represents the worst case.

In a full heap of N items, there are (N+1)/2 nodes at the leaf level. (N+1)/4 at the next level up. (N+1)/8 at the next, etc. You end up with this:
(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
...
That gives us the series:
((N+1)/2)*0 + ((N+1)/4)*1 + ((N+1)/8)*2 + ((N+1)/16)*3 ...
Let's see what that does for heaps of different sizes:
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
         ....
I ran that for heaps up of up to 20 levels (size a million and change), and it holds true: the maximum number of levels moved for a full heap of N items is N-log2(N+1).

Taking the above series as an Arithetico-geometric Sequence, we compute the sum for log2(N + 1) - 1 terms, ignoring the first term as it is zero, to be equal to N - 1. (Recall that a full binary tree has log2(N + 1) levels)

This sum represents the total number of times a siftup operation was performed. The total number of comparisons thus required is 2N - 2 (since each sift up operation requires two comparisons). This is also the upper bound, since a full binary tree always represents the worst case for a given tree depth.

                        
这篇关于证明二进制堆构建最大比较为（2N-2）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！