|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.AlSp-Heap History
Hide minor edits - Show changes to output
Added lines 2-4:
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
---- Changed line 171 from:
[[!UniCrema]] - [[!Programmazione]] to:
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]] - [[!Programmazione]]
Changed lines 51-53 from:
to:
Changed lines 75-77 from:
8 7 => 8 7 => 8
/ \ / / \ / \
10 12 9 10 12 10 12 to:
8 7 => 8 7 => 8 9
/ \ / / \ / \
10 12 9 10 12 10 12 Changed lines 111-113 from:
to:
Changed lines 1-3 from:
(:title Heap:)
%titolo%''':: Heap e Heapsort ::''' to:
(:title Heap e HeapSort:)
%titolo%''':: Heap e HeapSort ::''' Changed lines 88-92 from:
7 7
/ \
8 9 => 8 6
/ \ / / \ /
10 12 6 10 12 9 to:
7 7 6
/ \ / \ / \
8 9 => 8 6 => 8 7
/ \ / / \ / / \ /
10 12 6 10 12 9 10 12 9
Added lines 158-168:
!!!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@].
[[(Attach:)heapsort.java]]
----
[[!UniCrema]] - [[!Programmazione]]
Changed lines 118-157 from:
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. to:
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:
** '''min'''
** '''cancellamin'''
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:)
Changed lines 83-84 from:
L'operatore '''inserisci''' si realizza mettendo il nuovo elemento appena arrivato in fondo 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). to:
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). Added lines 94-118:
!!!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.
Added line 50:
Changed lines 52-53 from:
to:
Changed lines 73-76 from:
1 17
8 7 8 9
10 9 =>
11 13 17
to:
1 9 7
/ \ / \ / \
8 7 => 8 7 => 8 9
/ \ / / \ / \
10 12 9 10 12 10 12 Added lines 79-93:
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 fondo 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
/ \ / \
8 9 => 8 6
/ \ / / \ /
10 12 6 10 12 9
@]
Changed line 47 from:
Ecco una pessima rappresentazione di uno heap to:
Ecco una pessima rappresentazione di uno heap: Changed lines 50-52 from:
to:
8 7
10 12 9
11 13 15 20 17 Changed lines 55-76 from:
Si attende un volontario che faccia i disegnini. to:
(''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 17
8 7 8 9
10 9 =>
11 13 17
@]
Changed lines 45-55 from:
# un nodo contiene un elemento che è >= del padre (la relazione di ordinamento di prima). to:
# 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 9
11 13 17
@]
Si attende un volontario che faccia i disegnini.
Added lines 1-45:
(:title Heap:)
%titolo%''':: 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).
|
|
