Min Heapify method- Min heap algorithm

Question

I am trying to build a min heap. I have already done the insert, delete,swap, up-heap, down-heap and it is working correctly.

However, I am trying to write a method for Min-Heapify.

Here is my Input: {20,14,9,6,4,5,1}

The output I expected would be for the min heap: {1,5,4,20,9,6,14} But What I got is : {14,6,9,20,4,5,1} which is the opposite.

Here is my code:

public void minHeapify(int parentIndex)
    {
        int left = getLeft(parentIndex);
        int right = getRight(parentIndex);
        int smallest = parentIndex;
        if(_size >right && _heapArray[left]<_heapArray[parentIndex])
        {
            smallest = left;
        }

        if(_size>left && _heapArray[right]<_heapArray[parentIndex])
        {
            smallest = right;
        }
        if(smallest !=parentIndex)
        {
            replace(parentIndex, smallest);
            minHeapify(smallest);
        }
    }

I followed this pseudocode for the MAX-Heapify

Heapify (A, i)
l ← left [i]
r ← right [i]
if l ≤ heap-size [A] and A[l] > A[i]
then largest ← l
else largest ← i
if r ≤ heap-size [A] and A[i] > A[largest]
then largest ← r
if largest  ≠ i
then exchange A[i] ↔ A[largest]
Heapify (A, largest)

Sidonia

Answer 1

There is a typo in the part that is supposed to check the left child. The line

if(_size >right && _heapArray[left]<_heapArray[parentIndex])

should be

if(_size >left && _heapArray[left]<_heapArray[parentIndex])

There is a similar typo on the right side (looks like you replaced the left and right in the wrong place), but there is also a more serious logical bug. The following line:

if(_size>left && _heapArray[right]<_heapArray[parentIndex])

Should actually be (correcting for the typo and the logical bug):

if(_size>right && _heapArray[right]<_heapArray[smallest])

Because you need to pick whichever is smaller of left or right. If you only check _heapArray[right]<_heapArray[parentIndex] then you'll swap the parent with the right child whenever the right child is smaller than the parent, even when the left child is smaller than the right child.

Incidentally, you could also check against heapArray[smallest] instead of heapArray[parentIndex] on the left side, since you initialize smallest to parentIndex earlier.

Dorsoventral