Concetti Chiave
- L'heap è una struttura dati dinamica che si presenta come un albero binario, utile per implementare code a priorità e algoritmi di ordinamento.
- Ogni nodo padre dell'heap è maggiore di tutti i nodi discendenti, permettendo di trovare rapidamente il valore massimo nella radice.
- L'heap è memorizzato in un vettore dinamico, il che facilita la gestione della memoria e l'accesso ai nodi.
- La funzione heapBuild applica le caratteristiche strutturali dell'heap a un nuovo vettore di valori, partendo dall'ultimo nodo padre per garantire la corretta struttura.
- La funzione heapify mantiene le proprietà dell'heap nei sotto-alberi, verificando e scambiando i nodi se necessario per preservare l'integrità della struttura.
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.
Quali sono le caratteristiche dell'heap?
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.
struct heap{
int heapsize;
int *vett;
}
Creazione e gestione dell'heap
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;
}
Funzione heapify
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 ((r
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.
Domande da interrogazione
- Qual è la principale caratteristica strutturale dell'heap?
- Come viene creato un heap a partire da un vettore di valori?
- Qual è la funzione di heapify nell'ADT?
L'heap è caratterizzato dal fatto che ogni nodo padre è maggiore di tutti i nodi discendenti, permettendo così di trovare il valore maggiore nel nodo radice (come descritto nel testo).
L'heap viene creato utilizzando la funzione heapBuild, che applica le caratteristiche strutturali dell'heap a un nuovo vettore di valori partendo dall'ultimo nodo padre dell'albero (come spiegato nel testo).
La funzione heapify applica le proprietà dell'heap a tutti i sotto-alberi, garantendo che ogni sotto-ramo rispetti le caratteristiche strutturali richieste (come indicato nel testo).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
