Operazioni - Estrazione del nodo con chiave minima

L'operazione di estrazione del nodo minimo costituisce, per quel che riguarda gli Heap di Fibonacci, il lavoro più complesso in quanto prevede la ristrutturazione dello Heap, che nelle altre funzioni non é presente.
Infatti la funzione di estrazione del minimo (come si puo' vedere dallo ``pseudo-codice'') utilizza due funzioni ausiliarie il cui funzionamento è spiegato in seguito:

    ESTRAI-MIN() {
      minimo = FH->min; 
      
      if(FH->min != NULL) 
        for(ogni figlio x di FH->min)
          togli x dala lista dei figli di min;
          aggiungi x alla lista delle radici di FH;
	  
          x->ppadre = NULL;
          FH->nalberi = FH->nalberi + 1;
	  
        if(FH->nnodi == 1)
          FH->min = NULL;
          FH->nalberi = FH->nalberi - 1;  
        else
          FH->min = FH->min->pdestro;
          CONSOLIDATE();     <- funzione di ristrutturazione dello Heap
	
        FH->nnodi = FH->nnodi - 1;
        
      return minimo;
    }

La ESTRAI-MIN() accede direttamente al minimo grazie al campo min dello Heap, ``promuove'' ogni suo figlio a radice; se il minimo era l'unico nodo mette il campo min a NULL, altrimenti gli assegna il suo adiacente destro (che non necessariamente è realmente il nuovo minimo) ed esegue la funzione di restaurazione; infine viene appropriatamente aggiornato il campo contatore dei numeri di nodi dello Heap e viene ritornato il nodo con chiave minima. Chiaramente se lo Heap è vuoto viene ritornato NULL.

La CONSOLIDATE() ha il compito di ricompattere il più possibile gli alberi; tale operazione eseguirà ripetutamente i seguenti due passi:

-

trovare due radici con lo stesso grado;

-

``trasformare'' quella con chiave più piccola in un figlio di quella con chiave maggiore.

Il secondo dei due passi è effettuato dalla LINK, un'altra funzione ausiliaria il cui (semplice) funzionamento è spiegato in seguito. Vediamo una possibile implementazione della CONSOLIDATE:

    R[ ]:  vettore di puntatori alle radici (init: NULL),
           R[i] punta all'ultima radice di grado i incontrata 
    x, y:  puntatori alle radici correnti
    g:     contiene il grado dell'ultima radice considerata
  
    CONSOLIDATE() {
       R[i] = NULL per ogni i;
      
       for(ogni nodo nd della lista della radici di FH)
          g = nd->grado;
          x = nd;
	 
          while(R[g] != NULL)
             y = R[g];
	    
             if(x->chiave > y->chiave)
               swap(x, y);
	          
             LINK(y, x);
	    
             R[g] = NULL;
             g = g+1;
	  
          R[g] = x;
	 
       FH->min = NULL;
      
       for(ogni i fino alla fine di R[ ])
          if (R[i] != NULL)
            aggiungi R[i] alla lista delle radici;
	   
            if(FH->min == NULL)oppure(R[i]->chiave < FH->min->chiave)
                FH->min = R[i];
    }

Per ogni radice dello Heap controlla se è stata precedentemente incontrata un'altra radice con lo stesso grado: in caso affermativo quella con chiave minore viene ``linkata'' all'altra (con la chiamata della funzione LINK), il grado della radice-padre viene incrementato e viene effettuato nuovamente lo stesso controllo. In caso negativo invece, la radice viene memorizzata nel vettore $R[]$ alla posizione $i$, dove $i$ è il grado della radice stessa.
Infine viene aggiornato il campo min e ricreata la lista delle radici: viene scandito tutto il vettore $R[]$ inserendo una ad una ogni radice presente in esso.
La funzione LINK serve per fondere due alberi in uno; la radice di uno dei due (quella con chiave minore) diventa un nodo figlio della radice dell'altro:

    LINK(y, x) {
      togli y dalla lista delle radici di FH;
      
      aggiungi y alla lista dei figli di x;
      
      x->grado = x->grado + 1;
      y->marcato = false;
    }

Figura 3: (a): lo heap prima dell'estrazione; (b): viene estratto il minimo e tutti i suoi figli sono promossi a radice; (c): inizia la scansione della lista delle radici: $17$ ha grado 1; (d): $24$ ha grado $2$; (e): $21$ ha grado $0$; (f): $7$ ha grado $0$ $\Rightarrow$ $21$ linkato a $7$; (g): ora $7$ ha grado 1 $\Rightarrow$ $17$ linkato a $7$; (h): ora $7$ ha grado 2 $\Rightarrow$ $24$ linkato a $7$; (i): $23$ ha grado $0$; (j): $18$ ha grado $1$; (k): $52$ ha grado $0$ $\Rightarrow$ $52$ linkato a $23$; ora $23$ ha grado $1$ $\Rightarrow$ $23$ linkato a $18$; ` (l): $38$ ha grado $1$; (m): lo heap é finalmente restaurato!

In Fig. 3 è mostrato il processo di estrazione del minimo(ESTRAI-MIN) e di restaurazione dello Heap (CONSOLIDATE e LINK).

Per il calcolo del costo della ESTRAI-MIN è indispensabile assumere che esiste un limite superiore $D(n)=\log{n}$ al grado massimo di un nodo qualsiasi dello Heap di Fibonacci; questo fatto verrà dimostrato in seguito (sottosezione 2.10). Affinchè il costo della ESTRAI-MIN sia ottimale è ovvio che la dimensione di $R[]$ debba essere anch'essa ottimale in quanto tale vettore viene più volte scandito e questo fatto potrebbe fare aumentare il costo totale; la sua dimensione sará $O(\log{n})$ che è proprio il grado massimo che una radice può avere.
Dimostriamo ora che il costo ammortizzato della ESTRAI-MIN è $O(\log{n})$: un contributo pari a $O(\log{n})$ è dato dal ciclo che promuove a radice tutti gli $O(\log{n})$ figli del nodo minimo; vi sono poi l'inizializzazione del vettore $R[]$ (all'inizio della CONSILIDATE) e la ricreazione della lista delle radici dello Heap (alla fine della CONSOLIDATE) che consitono entrambe nello scandire $R[]$ e che quindi portano un contributo pari anch'esso a $\log{n}$.
Resta ora da considerare la parte centrale della funzione CONSOLIDATE, quella incaricata di trovare e fondere gli alberi di uguale dimensione; il ciclo in questione opera una scansione della lista delle radici: tale lista è al più $D(n)+t(FH)-1$ dal momento che è formata dalla vecchia lista delle radici ($t(FH)$) e dai figli del nodo con chiave minima (D(n)); inoltre ad essa è stato tolto il minimo (-1). Quindi il costo reale totale in questo caso è $O(D(n)+t(FH))$. Trovato il costo reale non resta che il calcolo del potenziale per avere al termine il costo ammortizzato. Il potenziale prima:
$\Phi(FH_{i-1}) = t(FH_{i-1}) + 2m(FH_{i-1})$
e dopo:
$\Phi(FH_{i}) = log(n) + 2m(FH_{i-1})$
$\Phi(FH_{i}) = D(n) + 2m(FH_{i-1})$
Notiamo subito che il potenziale di $FH_{i}$ è minore o uguale a quello di $FH_{i-1}$ in quanto il numero di radici dopo la ristrutturazione dello Heap è diventato al più $D(n)$ (esattamente come il numero di radici in uno Heap Binomiale).
Il costo ammortizzato come al solito è:
$\hat{c_i} = c_i + \Phi(FH_i)-\Phi(FH_{i-1})$
sostituendo i due potenziali:
$\hat{c_i} = O(D(n)+t(FH_{i-1})) + D(n)+2m(FH_{i-1}) - t(FH_{i-1})-2m(FH_{i-1})$
$\hat{c_i} = O(D(n)+t(FH_{i-1})) + D(n) - t(FH_{i-1})$
$\hat{c_i} = O(2D(n)) + t(FH_{i-1}) - t(FH_{i-1})$
$\hat{c_i} = O(D(n))$
dal momento che $D(n)$ è stato assunto come $\log{n}$, si ha:
$\mathbf{\hat{c_i} = O(log(n))}$