|
|
L’ impiego più famoso di un heap permette di abbassare drasticamente la complessità dell’ algoritmo di ordinamento di un vettore basato sulla intera ricerca del minimo. Si supponga che l’ intera sequenza di n elementi da ordinare sia memorizzata nel vettore A. E’ possibile ordinare gli elementi di A utilizzando una coda con priorità C, nella quale sono dapprima inseriti in sequenza tutti gli elementi, e dalle quale sono poi estratti gli elementi minimi. Il codice di programmazione in linguaggio C è:
Se si vuole ordinare il vettore A in modo crescente, si inverte la proprietà 3) degli heap, che diventa: “Ogni padre è maggiore dei propri figli”. Se la coda di priorità è realizzata con uno heap, la complessità della procedura ordina è O( n log n ). Dall’applicazione degli alberi decisionali sappiamo che la complessità del problema di ordinamento è omega( n log n) quindi l’algoritmo è ottimo. Benché la procedura ORDINA abbia complessità ottima se si usa uno heap, essa presento lo svantaggio di richiedere un doppio trasferimento di elementi; dal vettore A allo heap e dallo heap di nuovo nel vettore A. E’ possibile però effettuare l’ ordinamento in loco, cioè direttamente nel vettore A, ma solo dopo avere ristrutturato A in modo che verifichi le proprietà di uno heap. E’ opportuno che dopo la ristrutturazione, A contenga l’ elemento massimo nella radice anziché il minimo (la ragione di questa scelta sarà più chiara in seguito). La ristrutturazione di A avviene richiamando più volte una opportuna procedura RESTAURAHEAP (A,i,j) che ricostruisce la sezione di heap compresa tra le posizioni i e j del vettore A, qualora il nodo A[i] sia minore di almeno uno dei suoi figli.
Se i >[j/2] allora i è una foglia e la procedura RESTAURAHEAP termina. Per esempio se facessimo una RESTAURAHEAP (A,3,5) dato che 3> 5/2 significa che l ‘elemento in posizione 3 del vettore A è una foglia. In altre parole in un vettore di n elementi solo i primi n/2 elementi (arrotondato per difetto) non sono foglie. Altrimenti, se la procedura non termina, si individua A[k] come il massimo tra A[2i] e A[2i+1] se esistono(passo1). Se A[i] < A[k] allora vengono scambiati tra loro A[i] e A[k] (passo2) ed avviene una chiamata ricorsiva nella porzione A[k…j](passo3). Costatato che è inutile richiamare la funzione RESTAURAHEAP più di n/2 volte rischiavamo la funzione di ristrutturazione in questo modo:
A questo punto la funzione heapsort può essere riscritta nel seguente modo:
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.