Gli Heap di Fibonacci

Gli Heap di Fibonacci furono introdotti verso la metà degli anni `70 da Fredman e Tarjan. In seguito lo stesso Tarjan, insieme a Driscoll, Sarnak e Sleator svilupparono gli "Heap rilassati" come alternativa agli Heap di Fibonacci. Nella nostra trattazione descriveremo solamentla prima delle due strutture di dati appena menzionate. I Fibonacci Heaps sono un'``ottima'' implementazione di Heap in quanto le operazioni più costose hanno complessità (ammortizzata) $O(\log{n})$ (e sono quelle che prevedono l'eliminazione di un elemento dall heap) mentre tutte le altre costano tempo (ammortizzato) costante^{2 3}:

	FIBONACCI HEAPS		BINOMIAL HEAPS
operazione	costo reale	costo amm.	costo reale
INSERISCI	$O(1)$	$O(1)$	$O(1)$
TROVA-MIN	$O(1)$	$O(1)$	$O(\log{n})$
ESTRAI-MIN	$O(\log{n}+t(H))$	$O(\log{n})$	$O(\log{n})$
UNIONE	O(1)	O(1)	$O(\log{n})$
DECREMENTA-CHIAVE	$O(\log{n})$	$O(1)$	$O(\log{n})$
CANCELLA	$O(\log{n}+t(H))$	$O(\log{n})$	$O(\log{n})$