堆积一个数组的最大比较次数是多少

Question

是否有一个通用公式来计算堆积n个元素的最大比较次数？

如果不是，13是堆积一个由8个元素组成的数组的最大比较次数吗？

我的理由是：

at h = 0, 1 node, 0 comparisons, 1* 0 = 0 comparisons 
at h = 1, 2 nodes, 1 comparison each, 2*1 = 2 comparisons
at h = 2, 4 nodes, 2 comparisons each, 4*2 = 8 comparisons
at h = 3, 1 node, 3 comparisons each, 1*3 = 3 comparisons
Total = 0 + 2 + 8 + 3 =13

Answer 1

公认的理论是，构建堆最多需要(2N-2(个比较。因此，所需的最大比较次数应为14次。我们可以通过检查一堆8个元素来很容易地确认这一点：

7
/   
3     1
/    / 
5   4 8   2
/
6

在这里，4个叶节点永远不会向下移动。节点5和1可以向下移动1级。3可以向下移动两个级别。7可能下降3级。所以级别移动的最大次数是：

(0*4)+(1*2)+(2*1)+(3*1) = 7

每个级别的移动都需要2次比较，因此最大比较次数为14次。