Min Heapify Method - Minimal Heap Algorithm

I'm trying to build a bunch of minutes. I already did insert, delete, swap, heap, heap, and it works correctly.

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

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

The expected result will be for the minimum heap: {1,5,4,20,9,6,14} But I have: {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 pseudo code for 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)
+5
source share
1 answer

There is a typo in the part that should check the left child. Line

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

it should be

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

Similar typo on the right side (it looks like you have replaced left, and rightin the wrong place), but there are more serious logical fallacy. Next line:

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

( ):

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

, left right. _heapArray[right]<_heapArray[parentIndex], , , , .

, heapArray[smallest] heapArray[parentIndex] , smallest parentIndex.

+12

All Articles