Heap binario

Un heap è una struttura dati utilizzata in informatica, più precisamente un albero binario quasi completo usato principalmente per la memorizzazione di collezioni di dati, dette dizionari.

Implementazione di un heap mediante Vettore

In ogni nodo è presente una coppia (k,x) in cui k è il valore della chiave associata alla entry x. Nei dizionari, a differenza delle mappe, ogni chiave può essere associata a più entry (come in un "reale" dizionario ogni parola ha più significati).
Questi tipi di albero hanno la seguente caratteristica: qualsiasi nodo padre ha chiave minore di entrambi (se esistono) i suoi figli.
In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo v dell'albero e scendendo nella struttura verso le foglie, si attraversano nodi con chiave sempre crescente (in senso lato).

Nell'immagine a fianco è possibile osservare quanto sopra descritto, in aggiunta si può dire che viene definito come last l'elemento che si trova più a destra nel livello delle foglie. Nell'esempio last assume il valore 15. Questo particolare nodo assume un compito determinante nei metodi per la rimozione della chiave minima (che è ovvio supporre, per le proprietà citate, si trovi nella radice) e nell'inserimento di una nuova chiave.

Code con priorità

Un problema classico dell'informatica è ordinare delle code di dati che possiedono una data priorità. Questo tipo di problema viene risolto utilizzato liste concatenate o alberi binari (heap).

Lista concatenata con priorità

Nell'implementazione attraverso liste concatenate, si ha in input un insieme di elementi (in quanto non è definita una relazione d'ordine dell'elemento ma è una proprietà intrinseca della sua priorità), e si otterrà una lista. Ad esempio se in input si ha

$C=\{12,7,2,8,3\}$ si otterrà una lista del tipo:

La posizione nella lista non è indicativa, ma lo è la priorità di ogni singolo elemento. Il costo della gestione della lista concatenata è troppo alto per questo motivo si opta per la soluzione tramite albero binario.

Albero binario con priorità

In questo tipo di implementazione ogni nodo contiene sia l'elemento che la priorità dell'elemento. Un albero è heap ordinato quando per ogni nodo il valore incontrato nel nodo stesso è maggiore o uguale al valore che si incontra nei figli del suddetto nodo (per maggiori informazioni heap sort). $\forall v$ $val(v)\geq val(v^{'})$ dove $v^{'}$ è il figlio di v.

Se un albero è heap ordinato, la radice contiene l'elemento con valore maggiore.

Albero binario head ordinato completo

E' un albero binario, heap ordinato, in cui tutti i livelli sono saturi, tranne che l'ultimo che risulta completo da sinistra verso destra. Questa tipologia di alberi nella programmazione viene sovente implementata attraverso l'utilizzo di vettori, comprendenti un numero N di celle (con indici da 0 ad N-1): la prima (indice 0) resta vuota, mentre nella posizione i=1 viene memorizzata la radice. Dato quindi un nodo nella posizione i, gli eventuali figli sono nelle celle 2i (sinistro) e 2i+1 (destro).

Costruzione di un heap

Nella costruzione di un heap si hanno due tecniche top-down (ossia si parte dalla radice) o bottom-up si parte dal fondo.

Rappresentazione top-down

Avendo in input il seguente vettore di partenza bisogna costruire un albero binario heap ordinato

$v=\{3,7,4,9,2,5,1,10,8\}$

File:Heap top down.gif

A livello di analisi delle complessità si possono riscontrare due casistiche. Nel caso migliore si ha un solo confronto per l'elemento che bisogna inserire e nessuno scambio e si ottiene una complessità di $O(1)$ ossia $\Theta (n)$ Nel caso peggiore ogni vaole che inserisco deve essere fatto risalire fino alla radice dato che è l'elemento massimo (il costo di questa operazione dipende dall'altezza attuale dell'albero). Il numero di confronti che vengono effettuati sono uguali a $\log _{2}n$ cioè l'altezza dell'albero per un totale di n nodi quindi si ha una complessità di $\Theta (n\log n)$

Costruzione Bottom-Up

In un albero binario completo che ha n nodi, si hanno ${\frac {n}{2}}$ foglie. Si parte dalla metà dell'array che rappresenta l'heap da costruire e si verifica che ogni nodo contenga un head ordinato. In un albero di altezza k avrò da gestire $n=\sum _{i=0}^{n}2^{i}=2^{k+1}-1$ .

Si inizia a considerare il primo nodo che non è una foglia si troverà a livello k -1. A questo livello si troveranno $2^{k-1}$ nodi. Ogni controllo se un nodo contiene un head ordinato sottostante utilizza 1 confronto tra i due fratelli e un confronto con il padre per un totale di 2 confronti. A livello k -1 si effettuano $22^{k-1}=2^{k}$ confronti.

Passando al livello k - 2 si effettuano $22^{k-2}=2^{k-1}$ quindi generalizzando al livello k - i si effettueranno Errore del parser (Errore di conversione. Server ("https://wikimedia.org/api/rest_") riporta: "Cannot get mml. upstream connect error or disconnect/reset before headers. reset reason: connection termination"): {\displaystyle 22^{k-i}=2^{k-i+1}} ossia

$\sum _{i=1}^{k}2i2^{k-i}$

Vediamo ora una rassegna dei principali metodi che sono associati ad una Priority queue, ovvero una struttura dati in cui in ogni momento è possibile associare una priorita' alle entry che ne fanno parte. In primo luogo analizziamo il metodo insert, attraverso il quale, come dice il nome stesso, si inserisce un nuovo nodo all'interno dell'albero:

insert (k, x)
INPUT chiave k, entry x
OUTPUT il nodo e inserito (in posizione opportuna) nel vettore che implementa l'heap
   e <- (k,x)
   P[++last] <- e
   while ((i > 1) AND (P[⌊i/2⌋].key() > P[i].key())
      scambia P[i], P[⌊i/2⌋]
      i <- ⌊i/2⌋
   return e

nell'algoritmo appare una tecnica di scorrimento dell'heap chiamata up-heap bubbling, ovvero, dato un indice i nell'array, si controlla se le proprieta' dell'albero sono verificate per i e per il suo padre, definito come la parte bassa di i/2.