Struttura degli Heap di Fibonacci

Gli Heap di Fibonacci sono un insieme di alberi con l'ordinamento parziale dello heap⁴; 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 intero⁵ 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.

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