# Heapify function bug?

I think there is a bug in the implementation of the heapify function. When the values are swapped there may be a case when the value of the child is greater than the parent. But the heapify recursion never goes back to parent, so i would end up with results like heapify([1,2,3,4,5]) => [ 3, 5, 1, 4, 2 ].

My implementation that solves this case is:

``````  const array = [...arr];
for (let i = 0; i < array.length; i++) {
heapify(i);
}
function heapify(index) {
let largerIndex = index;
const leftIndex = index * 2 + 1;
if (leftIndex < array.length && array[leftIndex] > array[largerIndex]) {
largerIndex = leftIndex;
}
const rightIndex = index * 2 + 2;
if (rightIndex < array.length && array[rightIndex] > array[largerIndex]) {
largerIndex = rightIndex;
}
if (index === largerIndex) return;

swap(index, largerIndex);
// this part is missing in the solution from the course
const parentIndex = Math.floor((index - 1) / 2);
if (array[parentIndex] < array[index]) {
heapify(parentIndex);
} else {
heapify(largerIndex);
}
}

function swap(firstIndex, secondIndex) {
const temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
return array;
};```

Is that correct?``````

After your swap, your code is chasing the parent in your next recursion rather than following the original value. You are kind of mixing a bubble up and bubble down. Your recursive calls should follow the original index value to its new home.

If it was swapped with a child, you then move to that child position (that now holds the original `array[i]` value) and check to see if it needs to be moved again.

If it wasnât swapped (i.e. the current position of `index[i]` is in the correct position), then the line `if (index === largerIndex) return;` would exit the recursion and collapse any remaining recursive calls on the stack so you can proceed to the next `i` value.

Make sense?

Can you provide the full implementation of heapify method?(without this bug)

This looked like a bug to me as well. 11-Solution-Heapify wonât âbubble upâ a max value if it is multiple children down from the top. (as far as I can see). The following entry, 12-Solution-Optimization, provides an algorithm that works.

Just got to this same lecture and it definitely has a bug. There are two main ways to heapify: you can go left to right and âbubble upâ or you can go right to left and âbubble downâ. If you try what Mosh is doing (left to right bubbling down) or its inverse (right to left bubbling up) then you will miss any values that âskipâ a level.

The simplest âfixâ for Moshâs implementation is to inverse the for loop so that you start from the last index and decrement:

``````for (var i = array.length - 1; i >= 0; i--) {
heapify(i);
}
``````
1 Like

Thanks you for suggesting going back, to check whether the item at the index isnât greater than itâs parent. Therefore calling heapify either with parent of larger item solved the problem.

The optimization also in video 12 solves the problem.

Here is my implementation:

``````static void heapify(int[ ] array) {
for (int i = 0; i < array.length; i++) {
heapify(array, i);
}
}
private static void heapify(int[] array, int index) {

var largerIndex = index;

var leftIndex = index * 2 + 1;
if (leftIndex < array.length &&
array[leftIndex] > array[largerIndex]) {
largerIndex = leftIndex;
}

var rightIndex = index * 2 + 2;
if (rightIndex < array.length &&
array[rightIndex] > array[largerIndex])
largerIndex = rightIndex;

if (index == largerIndex)
return;

swap(array, index, largerIndex);

var parentIndex = ((index - 1) / 2);

if (array[parentIndex] < array[index]) {
heapify(array, parentIndex);
} else {
heapify(array, largerIndex);
}
}
private static void swap(int[] array, int first, int second) {
int temp = array[first];
array[first] = array[second];
array[second] = temp;
}
``````
Summary

This text will be hidden

This worked for me. and it is pretty neat.