Torna alla pagina di Algoritmi e strutture dati
:: Heap e HeapSort ::
La PrioriCoda
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:
- creaprioricoda: () -> prioricoda
- inserisci: (tipoelem, prioricoda) -> prioricoda
- min: (prioricoda) -> tipoelem
- cancellamin: (prioricoda) -> prioricoda
Sono intuitive, no?
Realizzazioni
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.
Liste Ordinate
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:
- inserisci: O(n)
- min: O(1)
- cancellamin: O(1)
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.
Liste Non Ordinate
Viceversa: l'inserimento avviene nella prima posizione, mentre determinare il minimo e cancellarlo sono costose perché devo esaminare tutta la lista.
- inserisci: O(1)
- min: O(n)
- cancellamin: O(n)
Heap
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à:
- h è il livello massimo => ci sono 2^h - 1 nodi di livello minore di h
- tutte le foglie di livello h sono addossate a sinistra
- un nodo contiene un elemento che è >= del padre (la relazione di ordinamento di prima).
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.
Cancellamin
Il minimo sappiamo che è la radice. Per cancellare il minimo e riorganizzare il binalbero, dobbiamo fare le seguenti operazioni:
- copiare il valore dell'ultima foglia in basso a destra al posto del valore della radice
- eliminare l'ultima foglia in basso a destra
- fare in modo che questa nuova foglia occupi la posizione che gli spetta in mezzo all'albero, secondo la proprietà 3:
- prendo il minore dei suoi figli
- se è più grande di lui, la scambio con esso (per soddisfare la proprietà 3)
- ripeto il controllo con il minore dei suoi figli etc. finché non soddisfo la proprietà 3
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)!
Inserisci
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
Ecco fatto!
In questo modo, abbiamo una bella PrioriCoda realizzata con un albero binario con operatori ottimi:) Non vi sentite più felici e sollevati, ora?
Il vettore Heap
Il binalbero che rappresenta uno heap può essere mappato su di un vettore. Il sistema è il seguente:
- il primo elemento del vettore è la radice
- i figli di un nodo qualsiasi, che sta in posizione i, si troveranno in posizione 2i (figlio sx) e in posizione 2i + 1 (figlio dx).
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.
Realizzazione col vettore
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:)
Inserisci
- inserisco il nuovo nodo in fondo al mio vettore
- vado a recuperare il padre (posizione Padre = posizione Figlio / 2)
- soddisfo la proprietà 3? Se sì, fine, altrimenti:
- swappo il contenuto dei due nodi
- ora Figlio deve puntare alla posizione del Padre, e ora Padre deve puntare al Padre di questo nodo
- vado avanti a soddisfare l'ingorda proprietà 3.
Cancellamin
- copio il valore dell'ultimo elemento del vettore nella radice
- accorcio il vettore di 1
- prendo il minore dei figli della radice
- se soddisfo la proprietà 3, ok, altrimenti:
- swappo la radice con il suo figlio minore
- ripeto il controllo con i figli di questo nodo etc. etc.
HeapSort
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è:
- prendo il minor elemento di una lista e lo tolgo
- prendo il minor elemento della lista che rimane e lo tolgo
- prendo... etc.
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:)
- Per ogni elemento del vettore di origine, eseguo una inserisci nel mio heap
- Poi, ripeto fino ad esaurimento PrioriCoda:
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:)
HeapSort in Java
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.
heapsort.java
Torna alla pagina di Algoritmi e strutture dati - Programmazione
