Operazioni - Inserimento di un nuovo nodo

La funzione di inserimento nello Heap prevede che sia passato come parametro il valore della chiave del nuovo elemento; all'interno della funzione viene allocato lo spazio in memoria per il nuovo nodo:

   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.

Figura 2: (a): lo heap prima dell'inserimento; (b): lo heap dopo l'inserimento.

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

$$\Phi(FH_i) = t(FH_i)+2m(FH_i)$$

supponiamo che la $i$-esima operazione di una sequenza sia di inserimento:

$$\hat{c_i} = c_i + \Phi(FH_i)-\Phi(FH_{i-1})$$

il suo costo ammortizzato sarà:

$$\hat{c_i} = c_i + [t(FH_i)+2m(FH_i)] - [t(FH_{i-1})+2m(FH_{i-1})]$$

definiamo $t(FH_i)=k$ e $m(FH_i)=j$:

$$\hat{c_i} = O(1) + [k + 2j] - [k-1 + 2j] = O(1) + 1 = \underline{O(1)}.$$

Il costo ammortizzato è quindi costante.