Heapify function bug?

Data Structures
1

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?
2

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?

3

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

4

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.

5

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
6

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

7

This worked for me. and it is pretty neat.