Heapify function not working

Question

I have been trying to write a recursive heapify method that turns an array of integers into a min-heap. The Main and Heap classes are shown below. Most of the array shown in Main is already a min-heap, but the subtree [11, 4, 5] is not a min-heap. However, the heapify function doesn't seem to reach that subtree. I can't figure out what the problem is, any help would be greatly appreciated.

public class Heap { 
public Heap(int[] array) { 
    heap = array;
}

public void heapify() { 
    heapifyHelper(0);
}

public void heapifyHelper(int rootIndex) { 
    if(isLeafIndex(rootIndex)) { 
        return;
    }

    else { 
        int leftChildIndex = getLeftChildIndex(rootIndex);
        int rightChildIndex = getRightChildIndex(rootIndex);
        int leftChildValue = heap[leftChildIndex];
        int rightChildValue = heap[rightChildIndex];
        int rootValue = heap[rootIndex];

        if(leftChildValue < rootValue && leftChildValue < rightChildValue) { 
            swap(rootIndex, leftChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);
        }

        else if(rightChildValue < rootValue && rightChildValue < leftChildValue) { 
            swap(rootIndex, rightChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);

        }
    }
}

public int getLeftChildIndex(int parentIndex) { 
    return 2 * parentIndex + 1;
}

public int getRightChildIndex(int parentIndex) { 
    return 2 * parentIndex + 2;
}

public int getParentIndex(int childIndex) { 
    if(childIndex == 0) { 
        throw new IllegalArgumentException("Cannot get the parent index of the root.");
    }
    else { 
        return (childIndex / 2) - 1;
    }
}

public boolean isLeafIndex(int index) { 
    int leftIndex = getLeftChildIndex(index);
    int rightIndex = getRightChildIndex(index);
    if(leftIndex >= heap.length && rightIndex >= heap.length) { 
        return true;
    }
    else { 
        return false;
    }
}

public void swap(int index1, int index2) { 
    int temp = heap[index1];
    heap[index1] = heap[index2];
    heap[index2] = temp;
}

public void printHeap() { 
    System.out.println(Arrays.toString(heap));
}
int[] heap;
  }

public class Main { 
public static void main(String[] args) { 
    int[] x = {0, 5, 2, 9, 11, 6, 12, 21, 32, 4, 5};
    Heap heap = new Heap(x);
    heap.printHeap();
    heap.heapify();
    heap.printHeap();
}
 }

Answer 1

There are several problems in your heapifyHelper:

public void heapifyHelper(int rootIndex) { 
    if(isLeafIndex(rootIndex)) { 
        return;
    }

    else { 
        int leftChildIndex = getLeftChildIndex(rootIndex);
        int rightChildIndex = getRightChildIndex(rootIndex);
        int leftChildValue = heap[leftChildIndex];
        int rightChildValue = heap[rightChildIndex];

What if leftChildIndex == heap.length - 1? Then rightChildValue will cause an ArrayIndexOutOfBoundsException.

        int rootValue = heap[rootIndex];

        if(leftChildValue < rootValue && leftChildValue < rightChildValue) { 
            swap(rootIndex, leftChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);
        }

        else if(rightChildValue < rootValue && rightChildValue < leftChildValue) {

What if both children are equal, and smaller than the parent? In that case you don't swap at all.

            swap(rootIndex, rightChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);

        }
    }
}

And the reason why the subtree [11, 4, 5] isn't reached is because you only call heapifyHelper for the children if one of the children is smaller than the parent, but when you call heapifyHelper(1), the two children of the node 5 are 9 and 11, both larger than the root value. (Actually, you don't even call heapifyHelper(1), since heap[0]is already smaller than both its children.)

But rectifying that alone by unconditionally recurring (on the children that exist) doesn't make your heapify correct. If you recur from the root to the leaves, each value can bubble up at most one level. You must recur from the leaves to the root⁽¹⁾, and you need to sift the values down completely, not just one level.

If you only swap a value with one of its children, each position is considered at most twice. Once when comparing it to its parent, once when comparing it to its children. When you go from the root to the leaves, when you compare a position to its children, no position above it (no position with a smaller index, even) can ever be changed anymore.

So each value can bubble up at most one level. If the smallest element is below the direct children of root, root won't become the smallest element in the tree. If you start from the leaves (or rather the parents of the leaves), the values can bubble up as far as they need. But if you only swap a value with the smaller of its children (if that is smaller than the value), each value can still only bubble down one level, which still need not create a heap.

Let us consider the tree

     7
    / \
   /   \
  2     6
 / \   / \
1   3 4   5

If you go from the root to the leaves, you swap 2 and 7 first, giving

     2
    / \
   /   \
  7     6
 / \   / \
1   3 4   5

The top two levels are now a min-heap.

Then you treat the left subtree, and finally the right subtree, producing

     2
    / \
   /   \
  1     4
 / \   / \
7   3 6   5

altogether. Now the bottom two levels are composed of min-heaps, but the heap property was destroyed in the level above. To make that a heap again, the 1 must be sifted up further (in this case, just one level).

If you go from the leaves to the root, you first treat the right subtree,

  6
 / \
4   5

producing

  4
 / \
6   5

for that, then the left subtree

  2
 / \
1   3

producing

  1
 / \
2   3

there. Both subtrees are now min-heaps. Altogether, you have

     7
    / \
   /   \
  1     4
 / \   / \
2   3 6   5

Then you'd swap 7 and 1, producing

     1
    / \
   /   \
  7     4
 / \   / \
2   3 6   5

Now the root is the smallest value, but the last swap destroyed the heap property of the left subtree. To make that a heap again, the 7 must be sifted down further.

So you need a siftDown method (and/or a siftUp method) that sifts a value down (up) as far as needed.

private void siftDown(int index) {
    int leftChildIndex = getLeftChildIndex(index);
    if (leftChildIndex >= heap.length) {
        // a leaf, no further sifting down possible
        return;
    }
    int rightChildIndex = getRightChildIndex(index);
    if ((heap[leftChildIndex] < heap[index])
        && (rightChildIndex >= heap.length || heap[rightChildIndex] >= heap[leftChildIndex)) {
        // left child is smallest or only, and smaller than parent
        swap(index, leftChildIndex);
        siftDown(leftChildIndex);
    } else
        // left child not smaller than parent, or right child exists and is smaller than parent
        if (rightChildIndex < heap.length && heap[rightChildIndex] < heap[index]) {
            swap(index, rightChildIndex);
            siftDown(rightChildIndex);
        }
        // otherwise, this one has no smaller child, so no more sifting needed
}

Then a correct heapify would be

public void heapify() {
    // last index that has a child:
    int lastNonLeafIndex = heap.length/2 - 1;
    for(int index = lastNonLeafIndex; index >= 0; --index) {
        siftDown(index);
    }
}

That works because if you have a (binary) tree where both of the subtrees are min-heaps, sifting down the root value constructs a min-heap:

• If the root value is smaller than (or equal to) both its children, the entire tree is already a min-heap.
• Otherwise, after the root value has been swapped with the smaller of its children (without loss of generality the left), the other subtree is unchanged, hence still a min-heap. And, since the left child was the smallest value in the left subtree before the swap, the value at the root is the smallest value in the entire tree after the swap. Swapping may have destroyed the min-heap property of the left child, though. But the left-left and the left-right subtrees have not been changed, so they are still min-heaps. And the new left subtree is smaller than the original tree, so by the induction hypothesis, sifting down its root value creates a min-heap from that. So after sifting down has finished, we have a tree with the smallest value at the root, both of whose subtrees are min-heaps, that is, a min-heap.

Since each leaf is trivially a min-heap, for each index processed in heapify, the subtree rooted at that index becomes a min-heap.

The alternative, using siftUp:

private void siftUp(int index) {
    if (index == 0) return; // root, nothing to do
    int parentIndex = getParentIndex(index); // see Note below
    if (heap[index] < heap[parentIndex]) {
        swap(index, parentIndex);
        siftUp(parentIndex);
    }
}

public void heapify() {
    for(int index = 1; index < heap.length; ++index) {
        siftUp(index);
    }
}

The code for siftUp is much shorter than for siftDown, since only two nodes are involved here, and there is no need to check whether any child index falls outside the array. But the heapify is less efficient (see footnote ⁽¹⁾).

siftUp is the method used to insert a new value into a heap. So this one builds a heap by inserting all values (except the root value) into an existing min-heap [when siftUp(index) is called, the part of the array before index is already a min-heap].

Note: your getParentIndex is incorrect,

return (childIndex / 2) - 1;

says the parent of index 1 is -1, and the parent of index 3 is 0, correct is

return (childIndex - 1) / 2;

⁽¹⁾ Actually, you can proceed from the root to the leaves, if you sift each value up as far as needed. It's just more efficient to heapify going from the [parents of the] leaves to the root. If you go from the root to the leaves, at level k you have 2^k values that may need to bubble up k levels, which gives an O(n*log n) complexity for building the heap. If you proceed from the [parents of the] leaves upward, you have 2^(log n - 1 - k) values that may need to bubble down k levels, which gives a complexity of O(n) for building the heap.

Answer 2

So i think I figured out what the problem is.

Your heapify helper stops the minute you find a root where the root is smaller than leftChild and rightChild.

In running your case.. you reach a situation where root (5) is lesser than 11 and 9..But 11 is not heapified..

Many ways to fix this. That i leave to you.

EDIT So heapify is ideally meant only to put the first element in the rootIndex in a correct place. Not to create a Heap.

If you want to create a correct Heap, you need to insert a new element and call heapify on every such insert.