Nwlapcug.com


Come utilizzare un Heapsort in Java

L'algoritmo heapsort è uno degli algoritmi di ordinamento più veloce disponibili. I programmatori usano heapsort in Java perché è una buona scelta per le matrici molto grandi che sanno di essere in uno stato non ordinato. Per l'amor di efficienza, una struttura ad albero effettivo non viene utilizzata. Invece, l'albero è formata nel posto, proprio nella matrice. L'algoritmo heapsort è un algoritmo "sul posto", in quanto non richiede nessuna memoria aggiuntiva per eseguire l'ordinamento.

Istruzioni

1

Comporre il metodo di scambio. Questo si scambia due elementi della matrice.""public static void swap(int[] a, int i, int j) {
int tmp = a[j];
a[j] = a[i];
a[i] = tmp;
}""

2

Scrivere il nucleo dell'algoritmo, il metodo siftDown. Esso viene utilizzato per formare la struttura di heap sia fare il tipo effettivo.

3

Setacciare grandi valori verso la radice dell'albero e piccoli valori verso le foglie con il metodo siftDown. Come questo metodo viene chiamato più volte durante il processo di ordinamento, il più grande nodo è costantemente setacciato al nodo radice e spostato alla fine della matrice. Qualsiasi nodo n ha fino a due bambini, cui gli indici sono n 2 + 1 e n 2 + 2.""public static void siftDown(int[] a, int start, int end) {
int root = start;

while( root 2 + 1 <= end ) {
int child = root
2 + 1;

// If the child has a sibling and the child's value is less than its sibling
if( child < end && a[child] < a[child + 1] ) {
child++;
}

if( a[root] < a[child] ) {
swap(a, root, child);
root = child;
} else {
return;
}
}
}""

4

Utilizzare il metodo heapify. Questo metodo viene chiamato all'inizio del genere per creare la struttura di heap iniziale. Questo è fatto rapidamente, poiché la struttura di heap è un po ' vaga. L'unico requisito è che ogni nodo radice deve essere maggiore di nodi figlio.""public static void heapify(int[] a) {
for( int start = a.length / 2--1; start >= 0; start-- )
siftDown(a, start, a.length-1);
}""

5

Scrivere il metodo heapSort. Il metodo heapifies prima la matrice per preparare per l'ordinamento. Il metodo siftDown viene quindi chiamato nuovamente dal momento che il nodo principale è ora un piccolo valore. Questo setaccia un nuovo grande valore al nodo principale, e l'intero processo viene ripetuto fino a quando la dimensione dell'heap è uno.""public static void heapSort(int[] a) {
heapify(a);

for( int end = a.length--1; end > 1; end--) {
swap(a, end, 0);
siftDown(a, 0, end--1);
}
}""

6

Verificare il metodo di heapSort. Nell'esempio seguente viene illustrato un piccolo programma di test.""public static void main(String[] args) {
int[] a = new int[10];

for( int i = 0; i < 10; ++i ) a[i] = i+1;
for( int i = 0; i < 10; ++i )
swap(a, i, i + (int) (Math.random() * (9--i)));

System.out.println("Before sorting:");
for( int i = 0; i < a.length; ++i ) System.out.println(a[i]);

heapSort(a);
System.out.println("After sorting");
for( int i = 0; i < a.length; ++i ) System.out.println(a[i]);
}""

Consigli & Avvertenze

  • Anche se heapsort non è usato come spesso in Java come quicksort (perché quicksort è, in media, più veloce), il heapsort ha uno scenario peggiore più velocemente. Se del caso peggiore di quicksort è O(n^2), il caso peggiore di heapsort è O (n
  • Smax.
  • Poiché il metodo di siftDown passa al setaccio i valori più grandi nella parte superiore del mucchio (matrice di indice 0), a ogni iterazione del genere il nodo radice viene scambiato con l'ultimo nodo foglia, e la dimensione dell'heap viene decrementata. Si tratta di come è fatto l'ordinamento effettivo, spulciando grandi valori verso l'alto e spostarli fino alla fine.
  • Utilizzando una struttura ad albero reale sarebbe generare un sacco di nuovi oggetti, mettere carico sull'allocatore e garbage collector, utilizzare più memoria e prendere ulteriori accessi alla memoria.