Benvenuti in questa quinta lezione della serie “Scuola Serale di Italian Geek“.
Queste brevi lezioni sono state progettate in modo tale da risultare volutamente sintetiche, dunque, per approfondimenti contattateci usando i commenti a fine articolo. Il codice presente nelle lezioni e’ funzionante ed e’ stato testato su compilatore gcc version 3.4.6 20060404 (Red Hat 3.4.6-9).
L’indice delle lezioni si trova qui.
Heap
Un heap binario e’ una struttura dati composta da un array che puo’ essere considerato come un albero binario quasi completo.
Ogni nodo dell’albero corrisponde ad un elemento dell’array A che memorizza il valore del nodo. Quasi completo significa che tutti i livelli, tranne l’ultimo, sono completi: possono mancare alcune foglie consecutive a partire dall’ultima foglia a destra.
La “quasi” completezza garantisce che l’altezza di un heap con n nodi `e O(log2 n)
Vedremo che le operazioni fondamentali sugli heap vengono eseguite in un tempo che e’ al piu’ proporzionale all’altezza dell’heap e, quindi, richiedono un tempo O(log2 n).
Un array che rappresenta un heap binario `e un oggetto con due attributi:
- length[A] e’ il numero di elementi (la dimensione) dell’array
- heap-size[A] e’ il numero di elementi dell’heap memorizzati nell’array
La radice dell’albero e’ A[1] (si trova in posizione 1)
Se i e’ l’indice di un dato nodo, gli indici del padre parent[i ], del figlio sinistro left[i ] e del figlio destro right[i ] sono rispettivamente floor(i/2), 2i e 2i+1.
Di seguito i link per scaricare il pdf della lezione ed 2 file con il codice sorgente di esempio.
Download
- Lezione 5: Heap
- heap01.c
- heap02.c
La lezione precedente è stata Alberi rosso-neri.
Il prossimo appuntamento e’ per Venerdi’ 25 Novembre 2011, la lezione avra’ per argomento le Tabelle Hash.
Alla prossima!
Puoi seguire Massimo Orazio Spata, l’autore di questo post, su Twitter.
Sei veramente bravo in qualcosa e desideri condividere questa conoscenza con gli altri? Stiamo cercando collaboratori per creare altri corsi nella Scuola Serale di Italian Geek. Se sei interessato, scrivici all’indirizzo:[email protected]
Articoli Simili:
- Impara a Programmare, Lezione 4: Alberi rosso-neri
- Impara a Programmare, Lezione 3: Grafi ed Alberi
- Impara a Programmare, Lezione 1: Le Liste in C
Pacman
Nostradamus
Magical Cat Adventure
Snake