Introduzione all'ordinamento degli heap in Java

Heapsort in Java è una tecnica di ordinamento basata sul confronto, in cui viene utilizzata la struttura dati Binary Heap. Questo ordinamento è quasi uguale a quello dell'ordinamento di selezione in cui verrà selezionato l'elemento più grande e si posizionerà alla fine e il processo verrà ripetuto per tutti gli elementi. Per comprendere l'ordinamento dell'heap, vediamo quale ordinamento dell'heap binario in Java.

  • Struttura dei dati basata su alberi.
  • Albero binario completo.
  • Può avere fino a due figli.
  • Il valore nel nodo radice può essere maggiore (Heap massimo) o Più piccolo (heap minimo)

Come funziona Heap Sort in Java?

Prima di passare all'algoritmo, vediamo cosa è Heapify.

heapify

Dopo aver creato un heap con i dati di input, la proprietà heap potrebbe non essere soddisfatta. Per ottenerlo, verrà utilizzata una funzione chiamata heapify per regolare i nodi dell'heap. Se vogliamo creare un heap massimo, l'elemento corrente verrà confrontato con i suoi figli e se il valore di figli è maggiore dell'elemento corrente, lo scambio verrà effettuato con l'elemento più grande in un figlio sinistro o destro. Allo stesso modo, se è necessario creare min-heap, lo scambio verrà effettuato con l'elemento più piccolo nel figlio sinistro o destro. Ad esempio, il seguente è il nostro array di input,

Possiamo considerarlo come un albero invece che un array. Il primo elemento sarà root, il secondo sarà il figlio sinistro di root, il terzo elemento sarà il figlio destro di root e così via.

Per trasformare il mucchio in un albero, attraversa l'albero in una direzione dal basso verso l'alto. Poiché i nodi foglia non hanno figli, esaminiamo il livello successivo. cioè è 5 e 7.

Possiamo iniziare alle 5 come è a sinistra. Qui, 5 ha due figli: 9 e 4, dove 9 è maggiore del nodo genitore 5. Per allargare i genitori, scambiamo 5 e 9. Dopo lo scambio, l'albero sarà come mostrato di seguito.

Passiamo al prossimo elemento 7 dove 8 e 2 sono i bambini. Simile agli elementi 9 e 4, 7 e 8 verranno scambiati come nella struttura sottostante.

Infine, 3 ha due figli-9 e 8 dove 9 è maggiore tra i bambini e la radice. Quindi, lo scambio di 3 e 9 sarà fatto per rendere la radice più grande. Ripetere il processo fino a quando non si forma un heap valido come mostrato di seguito.

Algoritmo per Heap Sort in ordine crescente

  1. Crea un Max Heap con i dati di input
  2. Sostituisci l'ultimo elemento con l'elemento più grande nell'heap
  3. Heapify the Tree
  4. Ripetere il processo fino a quando l'array non viene ordinato

Algoritmo per l'heap in ordine decrescente

  1. Crea un heap minimo con i dati di input
  2. Sostituisci l'ultimo elemento con l'elemento più piccolo nell'heap
  3. Heapify the Tree
  4. Ripetere il processo fino a quando l'array non viene ordinato

Ora proviamo a ordinare l'heap ottenuto in precedenza in ordine crescente usando l'algoritmo indicato. Innanzitutto, rimuovi l'elemento più grande. vale a dire root e sostituirlo con l'ultimo elemento.

Ora, heapify l'albero formato e inserisci l'elemento rimosso nell'ultimo array come mostrato di seguito

Ancora una volta, rimuovi l'elemento radice, sostituiscilo con l'ultimo elemento e Heapify.

Inserire l'elemento rimosso nella posizione libera. Ora puoi vedere che la fine dell'array viene ordinata.

Ora, rimuovere l'elemento 7 e sostituirlo con 2.

Ammucchia l'albero, come mostrato di seguito.

Ripetere il processo fino a quando l'array non viene ordinato. Rimozione dell'elemento 5.

Accumulare l'albero.

Rimozione dell'elemento 4.

Accumulare di nuovo.

Alla fine, verrà formato un array ordinato come questo.

Esempi per implementare l'ordinamento dell'heap in Java

Ora, vediamo il codice sorgente di Heap Sort in Java

//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort (
public void sort(int array()) (
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) (
int x = array(0);//largest element(It is available in the root)
array(0) = array(i);
array(i) = x;
// Recursively call heapify until a heap is formed
heapify(array, i, 0);
)
)
// Heapify function
void heapify(int array(), int SizeofHeap, int i) (
int largestelement = i; // Set largest element as root
int leftChild = 2*i + 1; // index of left child = 2*i + 1
int rightChild = 2*i + 2; //index of right child = 2*i + 2
// left child is greater than root
if (leftChild array(largestelement))
largestelement = leftChild ;
//right child is greater than largest
if (rightChild array(largestelement))
largestelement = rightChild ;
// If largestelement is not root
if (largestelement != i) (
int temp = array(i);
array(i) = array(largestelement);
array(largestelement) = temp;
// Recursive call to heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
)
)
public static void main(String args()) (
int array() = (3, 5, 7, 9, 4, 8, 2);
System. out .println("Input array is: " + Arrays. toString (array));
HeapSort obj = new HeapSort();
obj.sort(array);
System. out .println("Sorted array is : " + Arrays. toString (array));
)
)

Produzione

Conclusione

L'ordinamento heap è una tecnica di ordinamento che dipende dalla struttura dei dati heap binari. È quasi simile all'ordinamento per selezione e non utilizza array separati per l'ordinamento e l'heap.

Articolo raccomandato

Questa è stata una guida a Heap Sort in Java. Qui discutiamo l'algoritmo funzionante, di ordinamento con ordine crescente e decrescente ed esempi con codice di esempio. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più -

  1. Funzioni matematiche JavaScript
  2. Layout in Java
  3. Compilatori Java
  4. Guida per unire l'ordinamento in Java
  5. Guida a Heap Sort in C
  6. Esempi di ordinamento di heap in C ++

Categoria:

Sviluppo software