给出一个测试案例，其中“算法简介”中的堆排序失败

Question

我正在阅读《算法入门》中的heapsort，那里说（1）以自底向上的方式构建最大堆。（2）然后与最后一个元素交换，并在第一个元素上调用max hepify，并继续这样。

让我们以这个输入为例-

->7 10 20 3 4 49 50

建立最大堆的步骤将是

7 10 50 3 4 49 20
7 10 50 3 4 49 20
50 10 7 3 4 49 20

这是最大的堆建立。现在我们与最后交换

20 10 7 3 4 49 | 50

现在我们在20上调用max heapify，什么也没有发生n我们将20放在n-1位置是错误的。

我们以自下而上的方式创建堆，但是以自上而下的方式调用heapify，我认为这就是为什么在此输入中给出错误的原因。

Answer 1

您建立最大堆的算法有错误。数组

50 10 7 3 4 49 20

不代表有效的最大堆。在传统的数组表示形式中，该数组将与此对应：

        50
    10      7
  3    4  49  20

这不是有效的堆，因为49和20比其父堆大。

您需要修复自下而上的堆构造算法。