Metodo Min Heapify - Algoritmo min heap

Question

Sto provando a creare un heap minimo. Ho già inserito, inserito, scambiato, up-heap, down-heap e funziona correttamente.

Tuttavia, sto provando a scrivere un metodo per Min-Heapify.

Ecco il mio ingresso: {} 20,14,9,6,4,5,1

L'uscita mi aspettavo sarebbe per il min heap: {1,5,4,20, 9,6,14} Ma quello che ho ottenuto è: {14,6,9,20,4,5,1} che è il contrario.

Ecco il mio codice:

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

Ho seguito questo pseudocodice per la 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

C'è un errore di battitura nella parte che dovrebbe controllare il figlio sinistro. La linea

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

dovrebbe essere

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

C'è un errore di battitura simile sul lato destro (sembra che è stato sostituito il left e right nel posto sbagliato), ma c'è anche una logica più grave bug. La seguente riga:

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

dovrebbe essere effettivamente (correzione per l'errore di battitura e il bug logica):

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

Perché è necessario scegliere a seconda di quale è più piccola di left o right. Se si controlla solo _heapArray[right]<_heapArray[parentIndex], si scambierà il genitore con il figlio giusto ogni volta che il figlio destro è più piccolo del genitore, anche quando il figlio sinistro è più piccolo del bambino giusto.

Per inciso, è anche possibile controllare heapArray[smallest] anziché heapArray[parentIndex] sul lato sinistro, poiché si inizializza smallest in parentIndex in precedenza.