Ordinamento: Heap Sort

Problema: Data una sequanza di $n$ numeri $A= [a_0,\, \dots\,, a_{n-1}]$, ordinarla in modo crescente.
Soluzione: Ricorsiva (Heap sort)
Complessità: $O(n \log n)$

L'idea alla base di Heap sort (o Heapsort) è quella di rappresentare una sequenza di $n$ numeri come fosse un albero binario con $n$ nodi con la proprietà che il valore di un nodo genitore è sempre $\ge$ al valore dei suoi due nodi figli.
Data, ad esempio, la sequenza nell'immagine sotto

un grafo che rispetta la proprietà appena descritta può essere questo.

Guardando gli indici sui nodi, la sequenza originaria dovrebbe quindi essere riordinata in

Questa sequenza si può ottenere da quella originaria notando che, se il valore del nodo all'$i$-esimo indice è minore di uno o entrambi i suoi figli, si può effettuare uno scambio tra il nodo genitore ed il figlio che ha massimo valore. Questa verifica non è necessaria per tutti i nodi del grafo. Ad esempio, non avrebbe senso eseguirla sulle foglie dell'ultimo livello di profondità del grafo (dall'indice $\lfloor n/2\rfloor$ in poi) poichè non hanno figli quindi sono gli elementi più grandi per definizione. Quindi si effettua la verifica in circa metà dei nodi complessivi. Effettuato un scambio, però, il nodo figlio che prende il valore del nodo genitore potrebbe dover eseguire la stessa verifica su se stesso per controllare che non sia diventato più piccolo di uno dei due suoi figli. Partendo dal nodo radice si vede che questo può succedere al massimo $\lfloor \log n\rfloor$ volte, che è proprio l'altezza del grafo.  Il costo computazionale, considerato che bisogna effettuare queste stesse operazioni per $n/2$ volte, è quindi $O(n \log n)$.
Alla fine di questo processo la sequenza rappresenta il grafo con le caratteristiche elencate all'inizio e così il primo elemento è inevitabilmente il più grande dell'intera sequenza. Scambiando questo elemento con l'ultimo, diminuendo la lunghezza della sequenza di 1 (escludendo di fatto l'elemento più grande) e riordinando con il procedimento appena visto questa sottosequenza, l'elemento più grande della sottosequenza arriva ancora al primo elemento e può essere scambiato nuovamente con l'ultimo. Ripetendo il procedimento per $n$ volte permette alla sequenza di essere ordinata in modo crescente. Il costo computazionale resta ($O(n \log n)$) dato che si effettueranno praticamente le stesse operazioni e su sottosequenze sempre più piccole.

Nel codice seguente vengono inseriti anche alcuni metodi di supporto che aiutano nell'implementazione di una coda di priorità massima. Per questo motivo si è deciso di mantenere variabili distinte per il numero di elementi della sequenza (length), numero di elementi della sottosequenza corrente (size) e lunghezza dell'array che contiene la sequenza di numeri (n).

/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di 
utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme 
C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono 
una maggiore semplificazione.*/
 
#include <stdio.h>
#include <math.h>
 
void print_vector(int *, int);
int parent(int);
int left(int);
int right(int);
void max_heapify(int *, int, int);
void build_max_heap(int *, int);
void heapsort(int *, int &, int);
int heap_max(int *);
int heap_extract_max(int *, int &);
void heap_increase_key(int *, int, int);
void max_heap_insert(int *, int, int &, int &, int);
 
int main(int argc, char *argv[], char *envp[])
{
 int arr[15] = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
 int size = 10;
 int length = 10;
 int n = sizeof(arr) / sizeof(int);
 heapsort(arr, size, length);
 print_vector(arr, length);
 return 0;
}
 
void heapsort(int *a, int &s, int l)
{
 build_max_heap(a, s);
 
 //commenta questa istruzione se non vuoi visualizzare la sequenza dopo build_max_heap()
 print_vector(a, s);
 
 for (int i = l - 1; i > 0; --i)
 {
  int t = a[i];
  a[i] = a[0];
  a[0] = t;
  --s;
  max_heapify(a, 0, s);
 }
}
 
void build_max_heap(int *a, int s)
{
 for (int i = s / 2 - 1; i >= 0; --i)
  max_heapify(a, i, s);
}
 
void max_heapify(int *a, int i, int s)
{
 int l = left(i);
 int r = right(i);
 int max;
 
 if (l < s && a[l] > a[i])
  max = l;
 else
  max = i;
 
 if (r < s && a[r] > a[max])
  max = r;
 
 if (max != i)
 {
  int t = a[max];
  a[max] = a[i];
  a[i] = t;
  max_heapify(a, max, s);
 }
}
 
int parent(int i)
{
 return ceil(i / 2) - 1;
}
 
int left(int i)
{
 return i * 2 + 1;
}
 
int right(int i)
{
 return i * 2 + 2;
}
 
int heap_max(int *a)
{
 return a[0];
}
 
int heap_extract_max(int *a, int &s)
{
 if (s < 1)
  fprintf(stderr, "%s\n", "Tentativo di estrarre da Heap di 1 solo elemento; " 
   "L'Heap deve contenere almeno un elemento!");
 else
 {
  int max = a[0];
  a[0] = a[s - 1];
  --s;
  max_heapify(a, 0, s);
  return max;
 }
}
 
void heap_increase_key(int *a, int i, int k)
{
 if (k < a[i])
  fprintf(stderr, "%s\n", "Valore minore di quello corrente; " 
   "Si può solo incrementare il valore di un elemento!");
 else
 {
  a[i] = k;
  while (i > 0 && a[parent(i)] < a[i])
  {
   int t = a[i];
   a[i] = a[parent(i)];
   a[parent(i)] = t;
   i = parent(i);
  }
 }
}
 
void max_heap_insert(int *a, int k, int &l, int &s, int n)
{
 if (l >= n || s >= n)
  fprintf(stderr, "%s %d\n", "Coda di priorità piena; Impossibile aggiungere elemento", k);
 else
 {
  ++s, ++l;
  a[s - 1] = k;
  heap_increase_key(a, s - 1, k);
 }
}
 
void print_vector(int *m, int n)
{
 for (int i = 0; i < n; ++i)
 {
  printf("%d ", m[i]);
 }
 printf("\n");
}

Riferimenti:
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Algoritmi in C - Sedgewick