給出一個測試用例，其中堆從排序算法出現故障

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 

Exchange現在我們所說的最大heapify月20日，沒有任何反應ñ我們將投入20 n-1個位置，這是錯誤的。

我們以自下而上的方式堆砌，但以自頂向下的方式調用heapify，我認爲這就是爲什麼它對這個輸入給出錯誤的原因。

Answer 1

您的構建最大堆的算法有錯誤。陣列

50 10 7 3 4 49 20 

不代表有效的最大堆。在傳統的數組表示，該數組將對應於這樣的：

 50 
    10  7 
    3 4 49 20 

這不是有效的，因爲堆49和20比它們的親本大。

您需要修復自下而上的堆構建算法。