为什么我们从下往上而不是从上而下构建最大堆

Question

问题：为什么我们希望BUILD-MAX-HEAP第2行中的循环索引＜code＞i到1，而不是从1增加到⌊长度[A]/2⌋ ？

算法:(算法入门书):

我试着用下面的图来展示这一点。

方法1：如果我们以相反的方式应用构建堆，从1到数组A=的长度[A]/2

方法2：如果我们以与＜code＞相反的方式应用构建堆⌊长度[A]/2⌋ 并减少到数组A的1=

问题:我发现在这两种情况下，父树大于其子树的堆属性都被保留，所以我不明白为什么一个解决方案说会有这样的问题，“我们不被允许调用MAX-HEAPIFY，因为它不满足子树是max-heaps的条件。也就是说，如果我们从< code>1开始，就不能保证< code>A[2]和< code>A[3]是max-heaps的根。

Answer 1

问题是你只能依靠MAX_HEAPIFY来完成它的工作，当根在i的子树在任何地方都服从堆属性时，除了根值（at i）本身，这可能需要向下筛选。MAX_HEAPIFY的工作只是将根的值移动到它的正确位置。它不能修复任何其他违反堆属性的行为。但是，如果保证i下面的树的其余部分服从堆属性，那么您可以确定在MAX_HEAPIFY运行后，i处的子树将是堆。

因此，如果您从top node开始，那么谁知道您将获得什么...树的其余部分不应服从堆属性，因此MAX_HEAPIFY不会（必然）传递堆。而且以自上而下的方式继续工作也无济于事。

如果我们采用html" target="_blank">示例树并执行前向循环替换，那么我们首先在该树上调用MAX_HEAPIFY（1）：

       5
      / \
     3   17
    / \
  10   84

...然后5将与17（位置3）交换，然后我们将在该节点上递归调用MAX_HEAPIFY（3），这将无济于事。所以我们会得到：

       17
      / \
     3   5
    / \
  10   84

接下来，我们调用MAX_HEAPIFY（2），它将用84交换3：

       17
      / \
     84  5
    / \
  10   3

在值为3的节点上再次进行递归调用，但这不会做任何事情。

这是前向循环替代中< code>MAX_HEAPIFY的最后一次调用...我们可以看到，值84没有机会找到它应该在的顶端。