Descrizione e analisi di una struttura dati avanzata: il Fibonacci Heap

Description and analysis of an advanced data structure: the Fibonacci Heap

In questa tesi viene presentata e analizzata la struttura dati Fibonacci heap, introdotta da Fredman e Tarjan, che rappresenta una delle soluzioni per l'implementazione di code di priorità. Dopo aver descritto la struttura del Fibonacci heap e le operazioni (Make-Heap, Insert, Union, Extract-Min, Decrease-Key, Delete), si introducono gli strumenti teorici necessari per la loro analisi, in particolare l'analisi ammortizzata tramite metodo del potenziale e le proprietà degli alberi binomiali. Si dimostra con l'utilizzo dell'analisi ammortizzata che Insert, Union e Decrease-Key hanno costo O(1), mentre Extract-Min e Delete hanno costo O(log n). Una parte rilevante della trattazione è dedicata a dimostrare che il grado massimo di un nodo è O(log n) grazie al legame con la crescita dei numeri di Fibonacci. La tesi si conclude con un confronto tra teoria e pratica.