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，这些名字彼此相似，不会告诉读者他们做了什么。

除此之外，没有太多可说的。