如果我们以自上而下的方式迭代 build-max-heap 会发生什么

Question

如果我们以自上而下的方式构造构建堆，时间复杂度很短，有什么缺点calculation.in使用第一种buid-max-heap堆算法比常用的第二种算法简单

Build-max-heap(A)
{
   A.heap-size=A.length
   for(i=1 to [A.lenth]/2)
   max-heapify(A,i)
}

Build-max-heap(A)
{
   A.heap-size=A.length
   for(i=[A.lenth]/2 downto 1)
   max-heapify(A,i)
}

Answer 1

正如所写，您的第一个示例不会执行任何操作，因为 i 小于 [A.length/2]。我怀疑你的意思是你的第一个例子是：

for (i=1 to [A.length]/2)

假设这就是您的意思，从上到下执行 min-heapify 不会产生有效的堆。考虑原始数组 [4,3,2,1]，它表示这棵树：

        4
      3   2
    1

在第一次迭代中，您想将 4 向下移动。所以你用最小的 child 交换它并得到数组 [2,3,4,1].

接下来，您要过滤 3。因此您将其与最小的 child 交换，得到 [2,1,4,3]。您现在已经完成了，您的 "heap" 看起来像这样：

        2
      1   4
    3

这不是一个有效的堆。

当您从中间向上移动时，最小的项目可以过滤到顶部。但是，当您从上往下进行时，最小的项目可能永远无法到达顶部。

Answer 2

最大或最小堆是嵌套最大或最小函数的实现，例如max(max(max(a, b), max(c, d)), ...)，它是所有个数组元素的min()或max()的一种表达式树，也就是你在实现max(a, b, c, ...) 或 min(a, b, c, ...)。要产生正确的结果，您需要收集要比较的最小或最大元素。为此，您需要对底部元素进行广泛比较，然后向上，将需要比较的元素数除以每个级别 2（每个级别消除一半）。从上到下不会产生正确的结果；您正在执行错误的表达式。

如果我们以自上而下的方式迭代 build-max-heap 会发生什么

What happens if we iterates build-max- heap in Top Down Manner

algorithm

heap

max-heap