Introduksjon til Heap Sort In Java

Heapsort i Java er en sammenligningsbasert sorteringsteknikk, der datastruktur Binary Heap brukes. Denne sorteringen er nesten den samme som for utvalgssortering der det største elementet blir valgt og plasseres til slutt og prosessen vil bli gjentatt for alle elementene. For å forstå Heap Sort, la oss se hva Binary Heap Sort i Java.

  • Trebasert datastruktur.
  • Komplett binærtre.
  • Det kan ha opptil to barn.
  • Verdien i rotnoden kan være større (Max Heap) eller Mindre (Min Heap)

Hvordan fungerer Heap Sort i Java?

Før vi går over til algoritmen, la oss se hva som er Heapify.

Heapify

Etter at det er opprettet en bunke med inndataene, kan det hende at bunkeegenskap ikke er fornøyd. For å oppnå det, vil en funksjon som kalles heapify brukes til å justere nodene til haugen. Hvis vi ønsker å opprette maksimal haug, vil det gjeldende elementet sammenlignes med dets barn, og hvis verdien til barn er større enn det nåværende elementet, vil bytte utføres med det største elementet i et venstre eller høyre barn. Tilsvarende, hvis det må opprettes min-haug, vil det bli byttet med det minste elementet i venstre eller høyre barn. For eksempel er følgende vårt input-array,

Vi kan betrakte dette som et tre i stedet for en matrise. Det første elementet vil være rot, det andre vil være det venstre barnet til roten, det tredje elementet vil være det rette barnet til roten og så videre.

For å forvandle bunke til et tre, krysser treet i en ned-opp retning. Siden bladnodene ikke har barn, la oss se nærmere på neste nivå. dvs. er 5 og 7.

Vi kan begynne klokka 5 som til venstre. Her har 5 to barn: 9 og 4, der 9 er større enn foreldreknuten 5. For å gjøre foreldrene større, bytter vi 5 og 9. Etter bytte vil treet være som vist nedenfor.

La oss gå til neste element 7 der 8 og 2 er barna. I likhet med elementene 9 og 4 vil 7 og 8 byttes som i treet nedenfor.

Endelig har 3 to barn-9 og 8 der 9 er større blant barna og roten. Så, bytte av 3 og 9 vil bli gjort for å gjøre roten større. Gjenta prosessen til det er dannet en gyldig bunke som vist nedenfor.

Algoritme for heap sortering i stigende rekkefølge

  1. Lag en Max Heap med inndataene
  2. Bytt ut det siste elementet med det største elementet i dyngen
  3. Heapify the Tree
  4. Gjenta prosessen til matrisen er sortert

Sortering i fallende rekkefølge

  1. Lag en Min Heap med inndataene
  2. Bytt ut det siste elementet med det minste elementet i dyngen
  3. Heapify the Tree
  4. Gjenta prosessen til matrisen er sortert

La oss prøve å sortere den oppnådde bunken i stigende rekkefølge ved å bruke den gitte algoritmen. Fjern først det største elementet. dvs. rot og erstatt det med det siste elementet.

Nå, heapify treet dannet og sett inn det fjernede elementet i den siste av arrayen som vist nedenfor

Fjern igjen rotelementet, erstatt det med det siste elementet og Heapify det.

Sett det fjernede elementet i den ledige stillingen. Nå kan du se at slutten av matrisen blir sortert.

Fjern nå element 7 og erstatt det med 2.

Heapify treet, som vist nedenfor.

Gjenta prosessen til matrisen er sortert. Fjerne element 5.

Heapifying treet.

Fjerne element 4.

Heapfying igjen.

Til slutt vil det bli dannet et sortert utvalg som dette.

Eksempler på Implement Heap Sort i Java

La oss se kildekoden til Heap Sort i 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));
)
)

Produksjon

Konklusjon

Heap Sort er en sorteringsteknikk som avhenger av strukturen Binary Heap Data. Den er nesten lik utvalgssortering og bruker ikke separate matriser for sortering og haug.

Anbefalt artikkel

Dette har vært en guide til Heap Sort i Java. Her diskuterer vi arbeid, sortering av algoritme med stigende og synkende rekkefølge og eksempler med eksempelskode. Du kan også gå gjennom andre foreslåtte artikler for å lære mer -

  1. JavaScript-matematikkfunksjoner
  2. Oppsett i Java
  3. Java-kompilatorer
  4. Guide to Merge Sort In Java
  5. Guide to Heap Sort in C
  6. Eksempler på Heap Sort i C ++

Kategori:

Programvare utvikling