Trovare i K numeri piu grandi tra N
Oggi vediamo come affrontare in maniera efficiente la ricerca dei K numeri più grandi tra N elementi.
Per semplicità affronteremo il caso di K=100 e N=1000000 quindi il nostro problema è
trovare i 100 numeri più grandi tra 1000000 dati.
Per farlo faremo uso di un binary heap (info su wikipedia). Un binary heap è un albero in cui i nodi rispettano sempre la relazione padre < figlio ( o figlio < padre). Per fare un esempio pensiamo al seguente albero
2
/ \
3 6
/ \ / \
4 7 8 9
L'algoritmo che vogliamo utilizzare è molto semplice ed è composto dai seguenti passi:
- si crea un binary heap con i primi 100 elementi del nostro vettore
- per i restanti elementi si controlla uno per uno se sono più grandi dell'attuale nodo radice e in caso affermativo si sostituisce la radice con l'elemento confrontato e si "aggiusta" l'albero.
Facciamo un esempio supponiamo che il prossimo valore da controllare sia M=5 e che l'albero attuale sia quello illustrato in alto. Essendo 5>2 sostituiamo il nodo radice
5
/ \
3 6
/ \ / \
4 7 8 9
Chiaramente questo non è un binary heap corretto. Dopo alcuni "swap" riusciamo a portarlo in una configurazione corretta
3
/ \
4 6
/ \ / \
5 7 8 9
Alla fine di questo ciclo il nostro albero conterrà esattamente i 100 numeri più grandi. Per costruire l'albero useremo un array e per farlo dobbiamo stabilire per ogni nodo chi sono i figli. Utilizzeremo la seguente strategia:
- l'elemento di indice 0 sarà la radice dell'albero
- gli elementi di indice 1 e 2 sono i figli della radice, gli elementi di indice 3 e 4 sono figli di 1 e gli elementi di indice 5 e 6 sono figli di 2
- in generale l'elemento di indice n ha come figli gli elementi di indice 2*n e 2*n+1
Riportiamo l'albero con indicati gli indici così come abbiamo deciso di organizzarli
0
/ \
1 2
/ \ / \
3 4 5 6
Per inizializzare l'array e quindi l'albero iniziale effettuiamo un sort sui primi 100 elementi dell'array di 1000000. Osserviamo che se K<<N il costo computazionale di tale operazione è minimo (sicuramente si può fare con K*log(K))
Abbiamo quindi bisogno di un metodo che "aggiusta" l'albero in caso sia necessario nei casi in cui la radice venga modificata. Abbiamo raccolto l'implementazione del tutto in una classe Heap
static class Heap { public static int[] DammiMax(int[] array,int Quanti) { int[] max = new int[Quanti]; max = array.Take(Quanti).ToArray(); Array.Sort(max); foreach (var item in array.Skip(Quanti)) { if (max[0] < item) { max[0] = item; Correct(max, 0); } } return max; } private static void Correct(int[] array, int index) { if (2 * index + 1 < array.Length) { if (array.ElementAt(2 * index + 1) < array[index]) { Swap(array, index, 2 * index + 1); Correct(array, 2 * index + 1); } if (2 * index + 2 < array.Length) { if (array.ElementAtOrDefault(2 * index + 2) < array[index]) { Swap(array, index, 2 * index + 2); Correct(array, 2 * index + 2); } } } } // swap inverte due nodi dell'albero private static void Swap(int[] array, int index, int firstChildIndex) { var aux = array[firstChildIndex]; array[firstChildIndex] = array[index]; array[index] = aux; } }
Per testare il tutto basta chiamare il metodo inserendo come parametri l'array di interi e il numero di "massimi" da estrarre.
Osserviamo che si potrebbero utilizzare al posto degli interi classi con un'implementazione dell'interfaccia IComparable.
comments powered by Disqus