INSERISCI(nuova_chiave) { new = allocazioneNuovoNodo(); new->chiave = nuova_chiave; new->grado = 0; new->ppadre = NULL; new->pfigli = NULL; new->marcato = false; inserisci new in testa alla lista delle radici; if(FHeap->min == NULL) oppure (FHeap->min->chiave > nuova_chiave) FHeap->min = new; FHeap->nnodi = FHeap->nnodi + 1; FHeap->nalberi = FHeap->nalberi + 1; }
Il nuovo elemento viene inserito in testa alla lista delle radici e vengono opportunamente inizializzati tutti i suoi campi; se necessario viene aggiornato il minimo dello Heap e infine vengono incrementati i contatori del numero dei nodi e del numero di radici.
A differenza delle funzioni di inserimento di altri tipi di heap (come per
esempio gli Heap Binomiali), questa funzione non si preoccupa di
ristrutturare in nessun modo la struttura dati. In questo senso si dice che
gli Heap di Fibonacci sono una struttura dati ``pigra'' poichè tende a
rinviare il lavoro; questo aspetto dimostra come il progetto degli Heap di
Fibonacci sia andato di pari passo con l'analisi ammortizzata delle
complessità delle sue operazioni.
Cerchiamo di determinare il costo ammortizzato di questa operazione:
il potenziale abbiamo detto che vale