FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 7. Gli heap.
Blue Glass Arrow RTL  6. Il paradigma "divide et impera"Crystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  8. Le tabelle di simboli
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

DefinizioniModifica

Coda a prioritàModifica

4 coda a priorità = struttura dati atta a mantenere un insieme S di dati aventi chiave e priorità → l'elemento inserito si posiziona nell'insieme a seconda della sua priorità, e l'elemento servito per primo è quello a massima priorità.

HeapModifica

Heap1

2 heap = albero binario con:

  • proprietà strutturale: tutti i livelli sono completi, tranne al più l'ultimo riempito da sinistra verso destra (albero quasi bilanciato);
  • proprietà funzionale: la chiave contenuta nel nodo padre è ≥ le chiavi contenute in ciascuno dei suoi sottoalberi figli → la chiave massima si trova nella radice (si considera solo > per escludere le chiavi duplicate).

ImplementazioneModifica

4 La coda a priorità si può implementare con l'heap, dove la priorità è in funzione del tempo di arrivo:

  • coda FIFO (coda): il primo che entra è il primo a uscire/essere servito (es. coda alla cassa);
  • coda LIFO (stack): l'ultimo che entra è il primo a uscire/essere servito (es. pila di libri).
Heap2

6 Si etichetta ogni nodo con un intero crescente. Ogni figlio sinistro ha indice 2i +1, ogni figlio destro ha indice 2i + 2. Per riempire l'heap, si usa un vettore e si scandiscono le celle contigue entro l'heap-size (= numero di elementi nell'heap).

ProcedureModifica

7 Le operazioni per trovare l'indice del figlio conoscendo quello del padre (o viceversa) sono efficienti. Un albero completo ha 2h + 1 − 1 nodi → per rappresentare l'heap seguente:

Heap3

si dovrebbe sovradimensionare il vettore a 15 celle, sprecando circa metà delle celle → è nel complesso ugualmente accettabile perché le operazioni sono comunque semplici.

Insert (complessità: T \left( n \right) = O \left( \log{n} \right))Modifica

8 Aggiunge una chiave in base alla sua priorità:

  • se il livello inferiore è già pieno, aggiunge un nuovo livello;
  • se il livello inferiore non è ancora pieno, aggiunge una foglia partendo da sinistra verso destra.

Per rispettare la proprietà funzionale dell'heap, confronta la chiave nuova con la chiave del padre: se la chiave del padre è inferiore, sposta il padre al livello inferiore e ripete l'operazione con il "nonno", arrivando al più alla radice.

Complessità

È un albero quasi bilanciato → la lunghezza del cammino-foglia è logaritmica nel numero di dati. Il caso peggiore è il percorrimento di un cammino radice-foglia, cioè il numero dei confronti massimi che eseguo è limitato dalla lunghezza massima del cammino radice-foglia → complessità: T \left( n \right) = O \left( \log{n} \right).

Heapify (complessità: T \left( n \right) = O \left( \log{n} \right))Modifica

13 Procedura di servizio che trasforma in un heap una terna (sottoalbero sinistro; radice; sottoalbero destro), con la condizione che i due sottoalberi sinistro e destro soddisfino già le proprietà dell'heap (caso particolare: foglia).

Passi
  • individua il massimo nella terna;
  • se il massimo è in uno dei sottoalberi, scambia la radice del sottoalbero con la radice;
  • scende ricorsivamente sul sottoalbero con cui è avvenuto lo scambio.

Caso peggiore: cammino radice-foglia.

Condizione di terminazione: la ricorsione arriva ad una foglia.

BuildHeap (complessità: T \left( n \right) = O \left( n \right))Modifica

Un heap si può costruire in due modi:

  1. si può inserire una serie di dati tramite operazioni di Insert consecutive in una struttura vuota;
  2. 17 tramite la procedura BuildHeap: partendo da un vettore di dati, lo interpreta come un albero binario, quindi applica operazioni di Heapify considerando terne dal basso verso l'alto e da destra verso sinistra → ciclo for discendente dall'indice dell'ultimo padre all'indice 0 della radice. Complessità: nonostante si effettuino \sim n operazioni di Heapify di costo \log{n}, si dimostra che la complessità non è linearitmica ma è: T \left( n \right) = O \left( n \right)

HeapSort (complessità: T \left( n \right) = O \left( n \log{n} \right) → algoritmo ottimo)Modifica

23 Passi

BuildHeap → scambio ultima_foglia-radice, ponendo quindi l'elemento massimo in fondo al vettore → ora lavora su un heap di dimensione heapsize − 1, che corrisponde alla parte sinistra non ancora ordinata del vettore → applica l'Heapify sull'heap rimanente (solo il primo elemento è fuori posto → evita la BuildHeap) → scambia ultima_foglia_corrente-radice → ...

AltreModifica

  • 3 maximum: ritorna l'elemento a priorità massima (complessità: T \left( n \right) = \Theta \left( 1 \right))
  • extract_max: estrae l'elemento a priorità massima (complessità: T \left( n \right) = O \left( \log{n} \right))
Blue Glass Arrow RTL  6. Il paradigma "divide et impera"Crystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  8. Le tabelle di simboli

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale