Torna alla pagina di Algoritmi e strutture dati
:: Heap e HeapSort ::
La PrioriCoda è una coda di priorità. Sappiamo già che le code sono strutture dati di tipo FIFO. La coda di priorità è una coda in cui gli elementi sono ordinati tramite una relazione di ordinamento globale. Questa può essere un >=, o un <=.
Da notare che le relazioni di ordinamento si scrivono <= o >= anche se non si tratta di numero, stiamo sempre parlando di tipi di dato in astratto.
Orbene, le PrioriCode (ma che nome è, sembra la coda dei Priori...) hanno queste specifiche:
Sono intuitive, no?
Come posso realizzarle? Ci sono tre alternative. La prima usa delle liste ordinate, la seconda delle liste non ordinate, e la terza infine (rullo di tamburi) lo heap.
Una lista ordinata è una lista in cui, quando inserisco un elemento, non lo metto nella prima posizione disponibile, ma controllo che sia soddisfatta la famosa relazione d'ordinamento globale e lo metto quindi al posto giusto. Ecco quindi che si spiega la complessità degli operatori:
min e cancellamin sono O(1) perché devo solo estrarre il primo elemento dalla lista, dato che l'inserimento è stato fatto rispettando l'ordine, e quindi è questo il motivo per cui inserisci costa così caro.
Viceversa: l'inserimento avviene nella prima posizione, mentre determinare il minimo e cancellarlo sono costose perché devo esaminare tutta la lista.
Lo heap è un vettore oppure un binalbero. Sì, avete capito bene: posso rappresentare uno heap indifferentemente come un vettore o come un binalbero. Lo heap serve per rappresentare in modo intelligente una prioricoda.
Per comodità, lo immagineremo come un albero binario, e poi spiegheremo come farlo diventare un vettore.
Ha queste tre proprietà:
Ecco una pessima rappresentazione di uno heap:
1
/ \
8 7
/ \ /
10 12 9
(Si attende un volontario che faccia i disegnini)
Come vedete, l'elemento minimo è in posizione radice, e man mano che si scende sono rispettate tutte le tre proprietà dello Heap. Se immaginiamo di mappare una prioricoda su di uno Heap, vediamo subito che l'operatore min costa O(1). Ed è già un vantaggio.
Rimangono gli operatori inserisci e cancellamin, i quali dovranno operare su questo binalbero.
Il minimo sappiamo che è la radice. Per cancellare il minimo e riorganizzare il binalbero, dobbiamo fare le seguenti operazioni:
Ecco una pessima rappresentazione grafica della cancellamin. L'albero è quello di prima, e voglio cancellare 1.
1 9 7
/ \ / \ / \
8 7 => 8 7 => 8 9
/ \ / / \ / \
10 12 9 10 12 10 12
Quanto è complesso questo operatore? Il numero di livello è dato da log_2(n), dove n è il numero dei nodi, quindi la complessità è O(n), perché nel caso peggiore sposto un valore dalla radice fino in fondo all'albero. .Un bel passo in avanti rispetto a O(n)!
L'operatore inserisci si realizza mettendo il nuovo elemento appena arrivato in basso a destra, così da essere l'ultima delle foglie, e lo si fa risalire fino a che non soddisfo la proprietà 3. Risalire vuol dire che lo scambio col suo padre se il suo padre è di valore superiore a lui. Nel caso pessimo, dovrò risalire fino alla radice, e quindi siamo ancora in O(logn).
Qui sotto inserisco un nodo di valore 6
7 7 6
/ \ / \ / \
8 9 => 8 6 => 8 7
/ \ / / \ / / \ /
10 12 6 10 12 9 10 12 9
In questo modo, abbiamo una bella PrioriCoda realizzata con un albero binario con operatori ottimi:) Non vi sentite più felici e sollevati, ora?
Il binalbero che rappresenta uno heap può essere mappato su di un vettore. Il sistema è il seguente:
I nodi del figlio in posizione 1, cioè la radice, staranno in 2*1 e in 2*1 + 1, cioè in pos 2 e 3. I figli di 2 staranno in 4 e 5, i figli di 3 in 6 e 7 etc. Praticamente si prende l'albero e si inseriscono i nodi per ogni livello, da sinistra a destra, e poi si va a capo con il livello successivo.
Questo sotto è l'albero iniziale:
1
/ \
8 7
/ \ /
10 12 9
Inserirò i nodi nel vettore in questo ordine: 1 - 8 - 7 - 10 - 12 - 9. Provate e vedrete che rispetta le specifiche del 2i, 2i + 1 etc.
Una conseguenza è che il padre di un qualsiasi nodo di posizione i, sta in posizione i/2. Tutto ciò è vero perché ad ogni livello aggiunto io raddoppio il numero di nodi dei livelli precedenti.
Adesso vediamo come realizzare lo heap col vettore. NON presento pseudocodice, perché lo si trova sul libro. Però sotto c'è un'implementazione dello heapsort in Java, e lì ovviamente il codice lo trovate... Si accettano tuttavia richieste in merito, e si vedrà di evaderle:)
Ed eccoci al piatto forte del menu odierno:) Lo HeapSort è un algoritmo per ordinare degli elementi, e si appoggia sulla struttura Heap testé descritta. Fino ad ora abbiamo usato il Selection Sort, cioè:
Insomma, O(n^2). Orrorrrre!
Lo HeapSort invece lavora infilando un vettore dentro uno Heap, ed estraendo poi il min per avere il vettore ordinato. È come se fagocitasse un vettore caotico e lo risputasse fuori in ordine:)
Siccome devo introdurre tutti i dati, e effettuare logn operazioni su di essi, la complessità del mio algoritmo HeapSort è O(nlogn), ed è il nuovo limite inferiore al problema dell'ordinamento!
C'è anche un modo per non usare una PrioriCoda esterna al vettore che devo ordinare, ma trasformare il vettore stesso in una PrioriCoda, ma questa è un'altra storia, e adesso non ho voglia di parlarne:)
Qui sotto trovate un bel programmino in Java, il quale implementa una PrioriCoda, e fa un bell'heapsort di un vettore, generato casualmente, secondo il sistema descritto qui sopra. Ho cercato di tradurre il codice scritto sul libro, con qualche eccezione dovuta alla chiarezza (ok non ho ecceduto in chiarezza) e soprattutto perché il libro assume i vettori con posizione iniziale a 1, mentre è noto che nella maggior parte dei linguaggi di programmazioni i vettori e gli array in genere partono da 0.
Per compilare il programma è necessario un Java >= 1.5, perché uso dei costrutti che nelle versioni precedenti non c'erano (Vector<Integer> per intenderci).
Si compila con javac heapsort.java e si esegue con java heapsort.
Torna alla pagina di Algoritmi e strutture dati - Programmazione