next up previous contents
Next: Operazioni - Creazione di Up: Gli Heap di Fibonacci Previous: Gli Heap di Fibonacci   Indice

Struttura degli Heap di Fibonacci

Gli Heap di Fibonacci sono un insieme di alberi con l'ordinamento parziale dello heap4; questi alberi non sono ordinati per grandezza come negli Heap Bonimiali e le loro radici sono poste in una lista bidirezionale (lo heap sarà sostanzialmente un puntatore a tale lista). Ogni nodo ha un puntatore al nodo-padre, un puntatore alla lista (bidirezionale) dei figli, un puntatore al suo fratello destro ed uno al suo sinistro. Inoltre ogni elemento ha un campo intero5 che contiene la sua chiave, un campo intero che contiene il suo grado (cioè il numero dei suoi figli) e un'altro campo booleano che indica se tale elemento è marcato, cioè se tale nodo ha perso un figlio dall'ultima volta in cui è diventato figlio di un altro nodo.
Uno Heap di Fibonacci è composto da un puntatore alla radice con chiave minima, un puntatore alla lista delle radici e due interi: uno che tiene conto del numero complessivo di elementi e l'altro del numero complessivo di alberi contenuti nello Heap. In Fig. 1 è mostrata una generica struttura di Heap di Fibonacci.

Figura 1: (a): rappresentazione di un possibile heap di Fibonacci; (b): lo stesso heap rappresentato con le liste delle radici e dei figli come nella reale implementazione; in nero sono rappresentati i nodi marcati.
\begin{figure}\mbox{
\epsfig{file=Images/04.eps, height = 13.0 true cm}}
\hspace{1.0cm}
\end{figure}

Lo Heap di Fibonacci possiede i seguenti attributi:

attributo descrizione
ptesta puntatore alla prima radice della lista
pmin puntatore alla radice con chiave minima
nnodi numero complessivo di nodi
nalberi numero complessivo di alberi

Ogni nodo dello Heap possiede i seguenti attributi:

attributo descrizione
ppadre puntatore al padre
pfigli puntatore alla lista dei figli
pdestro puntatore al fratello destro
psinistro puntatore al fratello sinistro
grado numero di figli
chiave valore del nodo
marcato indica se il nodo è marcato o no


next up previous contents
Next: Operazioni - Creazione di Up: Gli Heap di Fibonacci Previous: Gli Heap di Fibonacci   Indice
Paolo Larcheri 2002-01-26