1

如果我们用简单的时间复杂度计算以自顶向下的方式构建堆有什么缺点。简而言之，使用第一种构建最大堆算法而不是常用的第二种算法

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)
}
4

2 回答 2

1

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

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

假设这就是您的意思，从顶部向下执行min-heapify不会导致有效堆。[4,3,2,1]考虑代表这棵树的原始数组：

        4
      3   2
    1

在第一次迭代中，您希望将 4 向下移动。因此，您将其与最小的孩子交换并获得数组[2,3,4,1]。

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

        2
      1   4
    3

这不是一个有效的堆。

当您从中间向上时，最小的项目可以过滤到顶部。但是当你从上往下走时，最小的物品可能永远不会到达顶部。

于 2017-09-08T13:54:38.203 回答
1

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

于 2018-12-01T01:58:21.510 回答