Abdel-Raouf Abdel-Raouf - 9 months ago 35
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);
}
}

Answer Source

As you've noticed, min/max heaps made from a set of numbers can have multiple configurations of their leaves depending on the order in which they are inserted.

You might think this 'global ordering' of leaves might arise from some emergent behavior of the underlying heap property, but a given array doesn't have a one-to-one correspondence with a particular configuration.

This occurs because of how a child is inserted and bubbled-up (swapped with parents), which will stop as soon as it is smaller than it's parent - of which there can be multiple valid candidates for a position in the heap.

This was confusing to me when I first implemented a heap as well.