Heap

Da Wikipedia, l'enciclopedia libera.

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.

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 caratteristica secondo la quale 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).

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).
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.
Vediamo ora una rassegna dei principali metodi che sono associati ad una Priority queue, ovvero una struttura dati in cui in ogni momento e' 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.