|
|
Una coda di priorità è un particolare insieme, sugli elementi del quale è definita una relazione di ordinamento totale e in cui è possibile inserire un nuovo elemento ed estrarre l ‘elemento minimo. Le operazioni fondamentali sono simili a quelle del tipo dato “insieme”. Sono ammesse, oltre alla creazione, le operazioni di:
inserisci, per inserire un nuovo elemento
min, che restituisce il minimo dell’insieme
cancellamin, che rimuove l’elemento minimo
La specifica sintattica di queste operazioni é:
La specifica semantica con pre e postcondizioni di questi operatori è:
Si può realizzare una coda di priorità di n elementi utilizzando liste, ordinate o non. Nel caso di liste ordinate gli operatori min e cancellamin hanno complessità O(1) mentre inserisci è O(n). Viceversa, con liste non ordinate, inserisci è O(1) mentre min e cancellamin sono O(n). Supponiamo che il numero di elementi presenti nella coda con priorità possa essere limitato superiormente da una costante. Allora è possibile rendere uniforme la complessità degli operatori con una realizzazione sequenziale, efficiente e semplice, che usa un vettore chiamato Heap. L’idea è quella che sia possibile disporre gli elementi della coda C nel vettore H, o heap, affinché essi possano essere interpretati come un albero binario B. L’albero B deve verificare le seguenti proprietà:
se h è il livello massimo delle foglie, allora ci sono esattamente 2h-1 nodi di livello minore di h;
tutte le foglie di livello h sono addossate a sinistra;
ogni nodo contiene un elemento di C che è maggiore di quello contenuto nel padre.
Vediamo un esempio:
Ciascun livello k tranne l’ ultimo, (k = 0,…, h - 1) contiene tutti i 2k nodi. Pertanto gli n nodi di B corrispondono alle prime n posizioni del vettore H, tale che:
la radice di corrisponde alla prima posizione di H
il figlio sinistro del nodo nella posizione i-esima del vettore H è in posizione 2i
il figlio destro del nodo nella posizione i-esima del vettore H è in posizione 2i+1
In altre parole in vettore H conterrà i nodi dell’ albero B nell’ ordine in cui si incontrano i nodi visitando B per livelli crescenti ed esaminando da sinistra verso destra i nodi allo stesso livello. Quindi il vettore H dell’ albero B riportato sopra avrà il seguente aspetto:
Per esempio analizziamo il nodo in posizione 2 dell’ vettore H, il suo figlio sinistro sarà in posizione 2i quindi 2x2=4; il suo figlio destro sarà in posizione 2i+1 quindi 2x2+1=5. La realizzazione degli operatori min, cancellamin e inserisci è più semplice se si pensa di operare sull’albero B anziché sul vettore H. Ad esempio, per realizzare min basta leggere il valore contenuto nella radice dell’albero. Per eseguire “cancellami” si cancella la foglia di livello massimo più a destra (in modo da mantenere verificate le proprietà 1 e 2) , se ne copia l’ elemento nella radice, e si fa “scendere” tale elemento lungo un percorso radice-foglia, scambiando col minimo degli elementi contenuti nei figli, fino a verificare la proprietà 3.
Per eseguire “inserisci” si inserisce l’elemento come foglia più a destra del livello massimo (in modo da mantenere verificate le proprietà 1 e 2) e si fa “salire” il nuovo nodo con scambi padrefiglio lungo un cammino foglia – radice fino a verificare la proprietà 3. Nel seguente esempio viene inserito l ‘elemento 4.
L’applicazione principale del tipo di dato heap è quella dell’algoritmo di ordinamento heapsort.
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.