堆数组最大的比较次数是多少？

Question

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

如果不是，那么将堆8个元素组成的数组的最大比较次数是13吗？

我的推理是这样的：

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

这里，四个叶子节点永远不会向下移动。节点5和1可以向下移动1级。 3可以向下移动两个级别。而7则可以向下移动3个级别。因此，级别移动的最大数量为：

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

每个级别的移动都需要进行2次比较，因此最多可以进行14次比较。