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

Funzione Potenziale

Come detto in precedenza, il costo ammortizzato delle operazioni sugli Heap di Fibonacci è analizzato con il metodo del potenziale; è giunto quindi il momento di definire la funzione potenziale per questo tipo di struttura dati. Definiamo tale funzione:
$\Phi(FH_i) = t(FH_i)+2m(FH_i)$
dove $t(FH_i)$ è il numero di alberi e $m(FH_i)$ è il numero di nodi marcati dello heap dopo la $i$-esima operazione.
Questa equazione garantisce che un limite superiore al costo totale ammortizzato è anche un limite superiore al costo totale reale poichè $\Phi(FH_0)=0$ mentre $\Phi(FH_i)\geq0\newline\forall {i>0}$.



Paolo Larcheri 2002-01-26