MAX_HEAPIFY 实施

Question

我写了 JavaScript 代码来构建一个维护最大堆的 max heapify 属性，但是我有很多关于实现的问题：

array I test on: [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

有趣的问题；

只是为了确定，

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

也会return一个有效的数组。

因为目标只是提供一棵树

root 有最大值键
存储在 non-root 的键最多是其 parent
任何从根到叶的路径都是non-increasing顺序
左右sub-trees不相关

( http://www.cs.toronto.edu/~krueger/cscB63h/w07/lectures/tut02.txt )

算法交换 parents 和 children 直到满足这 4 个条件，所以是的，如果您从不同的数组开始，那么输出也会不同。

从 CodeReview 的角度来看：

MAX_HEAPIFY -> JavaScript 遵循 lowerCamelCase，所以 maxHeapify
您的缩进已关闭，请尝试使用 http://jsbeautifier.org/
为什么调用一个函数 MAX_HEAPIFY 和另一个函数 BuildMaxHeap，这些名称彼此相似并且不告诉 reader 它们的作用。

除此之外，没什么好说的了。

Answer 2

如您所见，min/max 由一组数字组成的堆可以有多种叶子配置，具体取决于插入顺序。

您可能认为这 'global ordering' 个叶子可能是由底层堆属性的某些紧急行为引起的，但是给定的数组与特定的数组没有一对一的对应关系配置。

发生这种情况是因为子项的插入方式和冒泡（与父项交换），一旦它小于父项就会停止 - 其中有可以是堆中一个位置的多个有效候选者。

当我第一次实现堆时，这也让我感到困惑。

MAX_HEAPIFY 实施

MAX_HEAPIFY implementation

javascript

heap

recursion