frammenti di razionalità

L’heapsort è un efficiente metodo di ordinamento caratterizzato da un costo computazionale nel caso peggiore pari a . Lo heapsort rientra nella classe degli algoritmi di ordinamento basati sui confronti e ha la particolarità di sfruttare una particolare struttura dati, lo heap binario.

Ecco la definizione formale di heap binario:

Un heap associato ad un insieme L di elementi è un albero binario radicato con le seguenti proprietà:

1. l’albero è completo fino al penultimo livello.
2. il valore dell’elemento in un nodo è sempre maggiore o uguale al valore degli elementi nei figli.

Un heap può esser rappresentato sia attraverso una struttura dati “puntata” (che fa uso di puntatori), sia attraverso un vettore posizionale (che è la rappresentazione usata nello heapsort). In un vettore posizionale, l’elemento di posto 0 è la radice dello heap, quello di posto 1 è il figlio sinistro della radice, quello di posto 2 è il figlio destro della radice. In generale possiamo scrivere che essendo l’indice di un nodo dello heap, il figlio sinistro avrà indice e quell destro avrà indice .

Nella letteratura, per convenzione, il vettore posizionale viene indicizzato a partire da 1; in questo caso, detto l’indice di un nodo, il figlio sinistro avrà indice e quello destro . In questo post, adotterò la prima forma di indicizzazione, perchè la reputo più adatta all’implementazione in C (in fondo, si tratta solo di aggiungere 1).

Lo heasort funziona in questo modo: per prima cosa occorre modificare il vettore da ordinare in modo che rispetti la proprietà dello heap che prevede che ogni nodo dell’albero contenga un valore maggiore o uguale al valore contenuto nei suoi figli. La funzione che si occupa di questo è la heap_build, che a sua volta fa ricorso alla funzione heap_heapify.

Ecco i sorgenti delle due funzioni:

inline void heap_heapify(int *v, int n, int i){
    int l=HEAP_LEFT(i);
    int r=HEAP_RIGHT(i);
    int largest=-1;

    if(l<=n-1){
        if(v[l]>v[i])
            largest=l;
        else
            largest=i;
    }

    if(r<=n-1)
        if(v[r]>v[largest])
            largest=r;

    if(largest!=i && largest>=0){
        swap_int(v+i,v+largest);
        heap_heapify(v,n,largest);
    }
}

inline void heap_build(int *v, int n){
    register int i;

    for(i=n/2-1;i>=0;i--)
        heap_heapify(v,n,i);
}

La funzione heap_build prende in input il vettore da “heapifizzare” e la dimensione dello stesso.

La funzione heap_heapify prende in input il vettore da “heapifizzare”, la sua dimensione e un intero i che indica il nodo dell’albero a partire dal quale dovrà iniziare la discesa ricorsiva.

Vediamo come funziona la heap_heapify. La prima cosa che viene fatta è il controllo tra il nodo i passato come argomento e i suoi figli per vedere quale nodo contenga il valore maggiore. Una volta che l’indice di questo nodo viene individuato, se tale indice è diverso dall’indice del nodo radice la funzione provvede a fare uno scambio dei valori e scende ricorsivamente sul nodo che conteneva il valore maggiore. Il motivo di questa implementazione è molto semplice: se ristabiliamo la proprietà di heap tra 3 nodi potrebbe accadere che i sottoalberi radicati nei figli del nodo i-esimo non soddisfino più tale proprietà; siamo quindi costretti a scendere di un livello per, eventualmente, aggiustare i valori dell’albero.

La heap_build chiama la heap_heapify a partire dal nodo di indice , che è il primo nodo interno dello heap. In pratica la heap_build si risparmia di “heapifizzare” le foglie dello heap, visto che banalmente sono sicuramente degli heap.

Dimenticavo, lo heap costruito dalla heap_build è caratterizzato da una struttura “rafforzata”: l’albero è completo fino al penultimo livello e le foglie sull’ultimo livello sono tutte compattate a sinistra.

Ecco il codice dello heap_sort:

inline void heap_sort(int *v, int n){
    register int i;

    heap_build(v,n);

    for(i=n-1;i>0;i--){
        swap_int(v,v+i);
        heap_heapify(v,i,0);
    }
}

L’algoritmo è molto semplice: dopo aver costruito uno heap a partire dal vettore v mediante la chiamata alla heap_build, ad ogni passo del ciclo for si scambia il primo elemento dello heap (che è l’elemento maggiore) con l’i-esimo elemento dello heap; successivamente viene chiamata la heap_heapify sul vettore di dimensione i a partire dal nodo radice.

Visto che il ciclo for conta all’indietro da a , di volta in volta il range di azione della heap_heapify si restringe di uno: ad ogni passo iterativo avremo la parte finale del vettore ordinata e la restante parte, dall’indice 0 a quello i, che presenta le caratteristiche di uno heap. In pratica, è un approccio simile a quello del selection sort.

All’inizio del post ho scritto che questo algoritmo ha un costo pari a . La dimostrazione di questa affermazione la troverete nel prossimo post!

Buon divertimento