algorithm - 给出一个测试用例，其中堆排序从 Introduction to Algorithm 失败

Question

我正在阅读《算法导论》中的堆排序，那里说(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 比它们的父堆大。

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