jump to navigation

Heapsort – implementazione 28 dicembre 2007

Posted by fripp in Algoritmi, C, Heapsort, Informatica, Ordinamento, Programmazione.
Tags: , , , , ,
trackback

L’heapsort è un efficiente metodo di ordinamento caratterizzato da un costo computazionale nel caso peggiore pari a O(n \log n). 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 i l’indice di un nodo dello heap, il figlio sinistro avrà indice 2\cdot i +1 e quell destro avrà indice 2 \cdot i +2.

Nella letteratura, per convenzione, il vettore posizionale viene indicizzato a partire da 1; in questo caso, detto i l’indice di un nodo, il figlio sinistro avrà indice 2 \cdot i e quello destro 2\cdot i +1. 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 \frac{n}{2}-1, 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 n-1 a 1, 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 O(n \log n). La dimostrazione di questa affermazione la troverete nel prossimo post!

Buon divertimento

Annunci

Commenti»

No comments yet — be the first.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: