Operazioni - Decremento di una chiave

Il vantaggio più grande offerto dallo Heap di Fibonacci è la possibilità di decrementare la chiave di un nodo in tempo (ammortizzato) costante. La funzione che decrementa la chiave di un nodo utilizza due funzioni ausiliarie il cui funzionamento è spiegato in seguito. Vediamo una possibile implementazione:

     pnd: puntatore al nodo la cui chiave va decrementata
     nk:  nuovo valore della chiave
     ppd: puntatore al padre
     
     DECREMENTA-CHIAVE(pnd, nk) {
        if (nk > pnd->chiave)
           Errore;
       
        pnd->chiave = nk;
        ppd = pnd->ppadre;
       
        if(ppd != NULL) e (pnd->chiave < ppd->chiave)
           TAGLIA(pnd, ppd);
           TAGLIO-A-CASCATA(ppd);
       
        if(pnd->chiave < FH->min->chiave)
          FH->min = pnd;
     }

Il primo passo consiste nel confrontare il nuovo valore della chiave con quello vecchio: se il vecchio è minore del nuovo è chiaramente restituito errore; in caso contrario il campo chiave del nodo assume il nuovo valore; in seguito si controlla se il padre del nodo in questione ha chiave maggiore del figlio: in caso positivo va ristabilita la proprità degli Heap secondo cui un nodo ha sempre chiave maggiore o uguale al padre (se questo esiste). Per compiere questo vengono chiamate le funzioni ausiliarie TAGLIA e TAGLIO-A-CASCATA. Come ultima cosa viene, se necessario, aggiornato il puntatore al minimo.
Funzionamento della funzione TAGLIO:

     TAGLIO(pnd, ppd) {
        toglie pnd dalla lista dei figli di ppd;
        
        ppd->grado =  ppd->grado -1;
        pnd->ppadre = NULL;
        pnd->marcato = false;
     }

Funzionamento della funzione TAGLIO-A-CASCATA:

     TAGLIO-A-CASCATA(pnd) {
       ppd = pnd->ppadre;
       
       if(ppd!=NULL)
         if(pnd->marcato == false)
            pnd->marcato = true;
         else
            TAGLIO(pnd, ppd);
            TAGLIO-A-CASCATA(ppd);    
     }

Per capire meglio il procedimento di decremento della chiave di un nodo e tutto quello che ne consegue è utile chiarirsi le idee con un esempio:

Figura 4: processo di decremento di una chiave e conseguenti tagli.

in Fig.4 sono raffigurati i vari stati dello Heap durante il decremento di due chiavi ed i successivi tagli:

(a)

stato iniziale dello Heap;

(b)

il nodo con chiave $46$ prende chiave $15$ e viene tagliato poichè la nuova radice è minore di quella del padre; la chiamata a TAGLIO-A-CASCATA marca a true il padre dal momento che ha appena perso il figlio;

(c)

il nodo con chiave $35$ prende chiave $5$ e viene tagliato poichè la nuova radice è minore di quella del padre; la chiamata a TAGLIO-A-CASCATA ``incontra'' il padre del nodo tagliato ($26$) che era in precedenza stato marcato (non importa quando); per questo viene tagliato, marcato a false e viene richiamata a sua volta la TAGLIO-A-CASCATA su suo padre...

(d)

la chiamata a TAGLIO-A-CASCATA ``incontra'' il padre del nodo tagliato ($26$) che era in precedenza stato marcato (non importa quando); per questo viene tagliato, marcato a false e viene richiamata a sua volta la TAGLIO-A-CASCATA su suo padre...

(e)

...dal momento che anche suo padre era stato marcato (vedi (b)) viene anch'esso tagliato e smarcato; a questo punto cessano i tagli a cascata perchè il nodo con chiave $7$ è una radice;

A cosa serve fare tutti questi tagli se concretamente sarebbe stato sufficiente fare solo il taglio del nodo la cui radice è stata decrementata?
La risposta è semplicissima: il procedimento permette alla DECREMENTA-CHIAVE di avere costo ammortizzato pari a $O(1)$: supponiamo che la TAGLIO-A-CASCATA sia richiamata $k$ volte dopo la chiamata a DECREMENTA-CHIAVE; il costo della DECREMENTA-CHIAVE stessa è $O(1)$ e cosí anche per la singola chiamata a TAGLIO-A-CASCATA (senza le chiamate ricorsive): quindi il costo reale della
DECREMENTA-CHIAVE è $O(k)$.
Il cambio di potenziale dello Heap:

$\Phi(FH_{i-1}) = t(FH_{i-1}) + 2m(FH_{i-1})$

Poichè il numero di alberi è aumentato di $k-1$ in $k$ chiamate a TAGLIO-A-CASCATA più il taglio del nodo decrementato abbiamo che:

$t(FH_i) = t(FH_{i-1}) + (k-1) + 1 = t(FH_{i-1}) + k$

Poichè il numero di nodi marcati è diminuito di $k-1$ unità nei tagli a cascata e puó essere stato aumentato di $1$ unità nell'ultima chiamata alla TAGLIO-A-CASCATA che può aver marcato un nodo, si ha:

$m(FH_i) = m(FH_{i-1}) - k + 2$

Dunque:

$\Phi(FH_i) = t(FH_{i-1})+k + 2m(FH_{i-1})-k+2$

La differenza di potenziale è quindi:

$\Phi(FH_i)-\Phi(FH_{i-1}) = k - 2k + 4 = 4 - k$

e il costo ammortizzato:

$\hat{c_i} = c_i + (\Phi(FH_i)-\Phi(FH_{i-1}))$
$= O(k) + 4 - k = \textbf{O(1)}\quad$

Ora risulta anche chiaro il motivo per cui la funzione potenziale degli Heap di Fibonacci sia stata definita con il doppio del numero di nodi marcati: in questo modo il costo ammortizzato della DECREMENTA-CHIAVE risulta essere costante.