Abdel-Raouf - 2 years ago 120
Javascript Question

# MAX_HEAPIFY implementation

I wrote JavaScript code to build a max heapify which maintains the max-heap property, but I have many questions regarding the implementation:

array I test on: [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

When I test on the array when it is sorted I got:

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

While unsorted I got:

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

Why or why not is the max-heapify affected by the array being sorted?

I find that when the array is sorted the solution is:

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

Why did I get a different solution when the array is sorted, even if I find my implementation is right according to the pseudocode in CLRS?

Could you specify another procedure that doesn't use recursion while achieving the same functionality?

``````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);
}
}
``````