Unnikked - Esperienze personali in campo informatico

HeapSort in Java

Gli algoritmi di ordinamento vengono utilizzati dappertutto il giorno d’oggi, le informazioni vengono ordinate per essere facilmente reperibili in futuro, basti pensare a google che indicizza e mantiene ordinate le pagine web (tramite altre strutture dati più complesse) per consentire agli utenti di ottenere le loro ricerche in meno di un secondo. Fin dall’inizio dell’era informatica molti teorici ha cercato di progettare algoritmi sempre più efficienti. Dallo studio fatto è emerso che non è possibile ordinare un array di n elementi in meno di Ω(nlogn) confronti (logaritmo intenso in base 2).

In questo articolo voglio presentarvi l’algoritmo heap sort che si basa sulla struttura dati heap con complessità temporale Ω(nlogn), in più tale algoritmo riesce ad ordinare anche in loco utilizzando lo stesso array per cui il suo costo in tempo di spazio in memoria è O(n) più lo spazio per i metodi ricorsivi di costruzione heap e aggiustamento.

L’algoritmo l’ho sviluppato in Java, utilizzando i generici, ciò significa che potrete utilizzare qualsiasi tipo Java su cui è definito una relazione di ordine totale tramite l’interfaccia Comparable.

Prima di proporre la classe HeapSort descrivo come funziona l’algoritmo senza scendere in troppi tecnicismi.

L’algoritmo come su detto si basta su una struttura dati di tipo heap. Un heap associato ad un insieme L di elementi è un albero binario radicato con le seguenti proprietà:

      • Struttura: l’albero è completo almeno fino al penultimo livello.
      • Contenuto informativo: gli elementi di L sono memorizzati nei nodi dell’albero; ogni nodo v memorizza uno ed un solo elemento e ogni elemento è memorizzato in un solo nodo.
      • Ordinamento a heap: il valore dell’elemento di un nodo è sempre maggiore o uguale al valore degli elementi nei figli.

max-heap

La proprietà sulla struttura di un heap implica che un heap con n nodi ha altezza θ(logn). Invece la proprietà ordinamento a heap implica che il massimo si trova sempre nella radice dell’heap.

Elencate le proprietà dell’heap l’algoritmo heap sort comprenderà di tre fasi:

      • dato un array A, generare velocemente l’heap corrispondente;
      • trovare il massimo nell’heap;
      • cancellare il massimo nell’heap;
      • generare l’array ordinato;

Trovare il massimo

Come detto in precedenza per la proprietà ordinamento a heap implica che il massimo si trova sempre nella radice dell’heap.

Cancellare il massimo

Per cancellare il massimo dalla radice eseguiamo i seguenti passaggi:

      • copiamo nella radice l’ultima foglia dell’heap
      • eliminiamo la foglia copiata
      • ripristiniamo la struttura ordinamento a heap

Il terzo passo è fondamentale per mantenere la proprietà ordinamento a heap poiché l’elemento che si trova nella foglia potrebbe inficiare tale proprietà. Per ripristinarla basta che ricorsivamente sia verificata la proprietà
ricorsivamente nel seguente modo: se il nodo v è una foglia, non bisogna fare niente, siamo arrivati alla fine dell’heap; altrimenti troviamo il figlio u di v con il valore massimo, se il valore di v è minore del valore di v scambiamo i valori e ricorsivamente richiamiamo la stessa funzione sul nodo u.

Costruzione dell’heap

Dal momento che utilizziamo lo stesso array, sfrutteremo la rappresentazione posizionale di un heap tramite l’utilizzo di un array i cui figli, sinisto e destro, si troveranno rispettivamente in posizione 2*i+1 e 2*i+2.

binary-heap-insertion-3

Notiamo che utilizzando il vettore posizionale la struttura ad albero gode di una struttura rafforzata: l’albero è completo fino al penultimo livello e le foglie sull’ultimo livello sono tutte compattate a sinistra.

La creazione dell’heap è una operazione che non richiede alcun confronto, dobbiamo solo spostare gli elementi dell’array per far rispettare la proprietà di ordinamento a heap. Utilizziamo la tecnica divide et impera per ripristinare tale proprietà. L’algoritmo per il ripristino della proprietà somiglia molto concettualmente all’algoritmo di visita post fissa (si visitano ricorsivamente prima il sottoalbero sinistro e poi quello destro di un nodo ed infine si visita il nodo stesso) di un albero binario, al posto della visita del nodo va richiamato su esso la procedura di aggiustamento dell’heap descritta nel paragrafo precedente.

Ordinare l’array

L’idea di ordinare in loco viene dal fatto che una volta eliminato il massimo dall’heap rimane uno spazio “vuoto” nell’array, in questa locazione può essere inserito il massimo estratto. Ripetendo per n volte questa procedura l’array viene ordinato.

Ecco il codice della classe HeapSort che ho scritto:

public final class HeapSort {

	public static <T extends Comparable<? super T>> void sort(T[] array) {
		int lastLeaf = array.length - 1;
		heapify(0, array);
		for(int i = 0; i < array.length; i++) {
			array[lastLeaf] = removeMax(lastLeaf, array);
			lastLeaf--;
		}
	}

	private static <T extends Comparable<? super T>> void fixHeap(int index, T[] heap, int lastLeaf) {
		if(2*index+1 > lastLeaf && 2*index+2 >lastLeaf) return;
		else {
			int maxChildIndex = maxChildIndex(index, heap, lastLeaf);
			if(heap[index].compareTo(heap[maxChildIndex]) < 0) {
				T tmp = heap[index];
				heap[index] = heap[maxChildIndex];
				heap[maxChildIndex] = tmp;
				fixHeap(maxChildIndex, heap, lastLeaf);
			}
		}
	}

	private static <T extends Comparable<? super T>> int maxChildIndex(int index, T[] heap, int lastLeaf) {
		if(2*index+1 > lastLeaf) return 2*index+2;
		if(2*index+2 > lastLeaf) return 2*index+1;
		return(heap[2*index+1].compareTo(heap[2*index+2]) < 0) ? 2*index+2 : 2*index+1;
	}

	private static <T extends Comparable<? super T>> void heapify(int index, T[]heap) {
		if(index >= heap.length) return;
		heapify(2*index+1, heap);
		heapify(2*index+2, heap);
		fixHeap(index, heap, heap.length-1);
	}

	private static <T extends Comparable<? super T>> T removeMax(int lastLeaf, T[]heap) {
		T max = heap[0];
		heap[0] = heap[lastLeaf];
		fixHeap(0, heap, lastLeaf-1);
		return max;
	}

	public static void main(String[] args) {
		Integer[] a = {84,2,7,3,25,14,35,65,88,4};
		System.out.println(java.util.Arrays.toString(a));
		sort(a);
		System.out.println(java.util.Arrays.toString(a));
	}
}