Min. Metoda Heapify - algorytm min. Sterty

Question

Próbuję zbudować stertę min. Wcześniej wstawiłem, usunąłem, zamienić, up-heap, down-heap i działa poprawnie.

Jednak staram się napisać metodę Min-Heapify.

Oto mój wkład: {20,14,9,6,4,5,1}

Wyjście spodziewałem byłoby dla min sterty: {1,5,4,20, 9,6,14} Ale to, co mam, to: {14,6,9,20,4,5,1}, co jest przeciwieństwem.

Oto mój kod:

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); 
     } 
    } 

Śledziłem ten Pseudokod dla 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) 

Answer 1

Jest literówka w części, który powinien sprawdzić lewy dziecko. Linia

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

powinny być

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

Jest podobny typo po prawej stronie (wygląda na to, zastąpił left i right w niewłaściwym miejscu), ale jest też bardziej poważne logiczne pluskwa. Następujący wiersz:

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

rzeczywiście powinny być (sprostowanie za literówki i logicznej bug):

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

Bo trzeba wybrać w zależności co jest mniejsze od left lub right. Jeśli sprawdzisz tylko _heapArray[right]<_heapArray[parentIndex], zamienisz rodzica na właściwe dziecko, gdy prawe dziecko będzie mniejsze od rodzica, nawet jeśli lewe dziecko jest mniejsze od prawego dziecka.

Nawiasem mówiąc, można również sprawdzić przed heapArray[smallest] zamiast heapArray[parentIndex] po lewej stronie, ponieważ wcześniej zainicjowano smallest na parentIndex.