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)