给出一个测试案例，其中“算法简介"中的堆排序失败 [英] Giving a test case where heap sort from Introduction to Algorithm fails

问题描述

我正在从算法入门中阅读堆排序，在那里说(1)以自下而上的方式建立最大堆.(2)然后与最后一个元素进行交换，并在第一个元素上调用max hepify，并继续这样.

I was reading heapsort from Introduction to Algorithms , It is stated there (1)To build max heap in bottom up manner. (2)Then exchange with last element and call max hepify on the first element and continues like this.

让我们以这个输入为例-

Lets take an example on this input-

->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

这是堆的最大堆积量.现在，我们与上一个

this is max heap build up. Now we exchange with last

20 10 7 3 4 49 | 50

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

now we call max heapify on 20, nothing happens n we will put 20 in n-1 position which is wrong.

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

We are making heap in the bottom up manner but calling heapify in top down manner, I think this is why its giving wrong on this input.

推荐答案

您建立最大堆的算法出错.数组

Your algorithm to build the max heap has an error. The array

50 10 7 3 4 49 20

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

Does not represent a valid max heap. In the traditional array representation, that array would correspond to this:

        50
    10      7
  3    4  49  20

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

That's not a valid heap because 49 and 20 are larger than their parent.

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

You need to fix your bottom-up heap construction algorithm.

这篇关于给出一个测试案例，其中“算法简介"中的堆排序失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！