Introduzione
Continuiamo ad occuparci heap parlando di come questa struttura dati possa essere utilizzata a nostro vantaggio per effettuare operazioni di ordinamento. Fortunatamente, se avete capito come funziona la costruzione di uno heap, Heapsort resta abbastanza semplice da comprendere. Nel caso aveste dei dubbi sugli heap, andatevi a leggere il nostro articolo sugli heap cliccando qua.
Spiegazione intuitiva
L’algoritmo Heapsort sfrutta il fatto che, riorganizzando gli elementi di un array per costruire un max-heap, si ritroverà sempre il massimo elemento in prima posizione, quindi con un ciclo for, trova ogni volta massimo elemento e lo scambia poi con l’elemento in ultima posizione, infine riorganizza gli elementi chiamando Max-Heapify sul sottoarray A heapsize – 1, dove A heapsize è la dimensione dell’heap in un array.
Preudocodice e descrizione dell’algoritmo
Scriviamo adesso lo pseudocodice ispirato dal libro Introduzione agli Algoritmi.
HeapSort(A)
Build-Max-Heap(A)
for(i = A.length downto 2)
exchange A[1] with A[i]
A.heapsize = A.heapsize - 1
Max-Heapify(A, 1)La prima operazione che viene eseguita quando viene chiamato Heapsort è quella di costruire sull’array una struttura heap attraverso la chiamata di Build Max-Heap.
Segue poi un ciclo for che parte dal’ultimo elemento dell’array fino ad arrivare al secondo indice, dove avvengono le seguenti operazioni:
- scambia l’elemento in prima posizione con l’elemento in ultima posizione, dato che quello in prima posizione possiede il valore più grande
- ridimensiona l’heap scartando la parte finale (-1 ad ogni ciclo), visto che è già ordinata
- chiama Max-Heapify sul sottoarray rimasto così da trovare il prossimo elemento massimo.
Vediamo questo disegnino che chiarirà eventuali dubbi 🙂
