# Algoritmi/Gli heap

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario

## Definizioni
### Coda a priorità

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à.

### Heap

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).

## Implementazione

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).
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).

## Procedure

Le operazioni per trovare l'indice del figlio conoscendo quello del padre (o viceversa) sono efficienti. Un albero completo ha 2$^{h+1}$ − 1 nodi → per rappresentare l'heap seguente:
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)$)

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)$)

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)$)

Un heap si può costruire in due modi:
* si può inserire una serie di dati tramite operazioni di Insert consecutive in una struttura vuota;
* 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)
#### 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 → ...

### Altre

* 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)$)