构建堆算法从中点开始，并根据需要向下移动项目。让我们考虑 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 个级别的堆（大小为 100 万并发生变化）运行了该方法，结果成立：N 个项目的完整堆移动的最大级别数为 N-log2(N+1)。
以上述系列为算术几何数列 https://en.wikipedia.org/wiki/Arithmetico%E2%80%93geometric_sequence，我们计算总和log2(N + 1) - 1项，忽略第一项，因为它为零，等于N - 1。 （回想一下，满二叉树有log2(N + 1) levels)
该总和表示执行 siftup 操作的总次数。因此需要的比较总数是2N - 2（因为每个筛选操作都需要两次比较）。这也是上限，因为完整二叉树始终代表给定树深度的最坏情况。
