MAX_HEAPIFY實施

Question

我寫的JavaScript代碼來構建一個最大heapify其保持最大堆屬性，但我有一個關於執行許多問題：

陣列I上測試：1，2，3，4 ，7，8，9，10，14，16]

當我測試時是排序我得到了陣列上：

[16，14，9，10，7,8 ，3,1,4,2]

雖然未排序的我：

[16，14，8，9，10，2，3，4，7，1]

爲什麼或爲什麼不是MAX-受數組排序影響的heapify？

我發現，當該陣列被排序的解決辦法是：

[16，14，10，8,7，9,3，2,4，1]

爲什麼當數組排序時，我是否得到了不同的解決方案，即使我發現我的實現是正確的，根據CLRS中的僞代碼？

你能指定，同時實現相同的功能，不使用遞歸另一個程序？

function BuildMaxHeap(array){ 
for(var i = Math.floor(array.length/2); i >= 0; i--){ 
    MAX_HEAPIFY(array, i); 
} 
return array; 
} 

function MAX_HEAPIFY(array, i) { 
var left = 2 * i + 1; 
var right = 2 * i + 2; 
var largest = i; 
if(left <= array.length && array[left] > array[largest]){ 
    largest = left; 
    } 
if(right <= array.length && array[right] > array[largest]){ 
    largest = right; 
} 
if(largest != i){ 
    var temp = array[i]; 
    array[i] = array[largest]; 
    array[largest] = temp; 
    MAX_HEAPIFY(array, largest); 
} 
} 

Answer 1

正如你已經注意到，從一組數字由最小/最大堆可以根據它們所插入的順序上都有它們的葉子的多種配置。

你可能會認爲葉的這種「全球性排序」可能會從底層堆屬性的一些緊急行爲出現，但給定的數組沒有一個一一對應與特定的配置。

這是因爲一個孩子是如何插入和冒泡式（交換與家長），這會盡快，因爲它是小於它的父站 - 其中有可能是在一個位置，多個有效候選人堆。

這是令人困惑的我，當我第一次實現了一個堆爲好。

Answer 2

有趣的問題;

只是可以肯定，

function buildMaxHeap(array){ 
return array.sort((a,b)=>b-a); 
} 

也將返回一個有效的數組。

由於目標是僅提供一個樹，其中

• 根部具有鍵最大值存儲在非根
• 關鍵是在它的父
• 從根的任何路徑的最值葉是在非遞增順序
• 左，右子樹無關

（http://www.cs.toronto.edu/~krueger/cscB63h/w07/lectures/tut02.txt）

名

算法互換家長和孩子，直到這些4個條件都滿足，那麼是的，如果你開始用不同的陣列，那麼也輸出可以是不同的。

從代碼審查的視角：

• MAX_HEAPIFY - > JavaScript的如下lowerCamelCase，所以maxHeapify
• 你壓痕是關閉的，請嘗試使用類似http://jsbeautifier.org/
• 爲什麼調用一個函數MAX_HEAPIFY和其他BuildMaxHeap，這些名字彼此相似，不會告訴讀者他們做了什麼。

除此之外，沒有太多可說的。