ADT Heap

ADT Heap

L’heap è una strutture dati dinamica implementata per semplicità quasi sempre come un ADT di prima categoria; si tratta, dal punto di vista logico, di un albero binario con determinate caratteristiche strutturali che rendono questa struttura dati particolarmente utile per l’implementazione di code a priorità, per ordinamenti e per svariati casi d’uso, permettendo di abbassarne il livello di complessità generale.
La peculiarità dell’heap è quella di essere memorizzato all’interno di un vettore dinamico e che ogni nodo padre sia, come numero intero, maggiore di tutti i nodi discendenti; grazie a questa caratteristica, ad esempio, il valore maggiore dell’heap si trova nel nodo radice.

Wrapper dell’ADT heap
struct heap{
int heapsize;
int *vett;
}

Durante la creazione dell’heap viene sfruttata la funzione heapBuild dell’ADT che si occupa di far valere le caratteristiche strutturali dell’heap al nuovo vettore di valori a partire dall’ultimo nodo padre dell’albero rappresentante l’heap:

void heapBuild (Heap h) {
int i;
for (i=(h->heapsize)/2-1; i >= 0; i--)
heapify(h, i);
return;
}

La funzione heapify dell’ADT si occupa di applicare le proprietà dell’heap a tutti i sotto-alberi passati alla funzione, rendendo quindi il sotto-ramo aderente alle proprietà strutturali richieste.
void HEAPify(Heap h, int i) {
int l, r, largest;
l = LEFT(i);
r = RIGHT(i);

if ((l heapsize) && (h->A[l]>h->A) )
largest = l;
else
largest = i;
if ((rheapsize)&& (h->A[r]>h->A[largest]))
largest = r;
if (largest != i) {
Swap(h, i,largest);
HEAPify(h, largest);
}
return;
}
La funzione LEFT restituisce l’indice del figlio sinistro, RIGHT quello del figlio destro e swap scambia semplicemente i nodi.