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

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次。

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

What is the maximum number of comparisons to heapify an array?

heap