Introduktion til Heap Sort In Java

Heapsort i Java er en sammenligningsbaseret sorteringsteknik, hvor datastruktur Binary Heap bruges. Denne sortering er næsten den samme som ved valg af sortering, hvor det største element vælges og placeres i slutningen og processen gentages for alle elementerne. For at forstå Heap Sort, lad os se, hvad Binary Heap Sort i Java.

  • Træbaseret datastruktur.
  • Komplet binært træ.
  • Det kan have op til to børn.
  • Værdien i rodnoden 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, så lad os se, hvad der er Heapify.

Heapify

Når der er oprettet en bunke med inputdataene, er heap-ejendom muligvis ikke tilfreds. For at opnå det bruges en funktion kaldet heapify til at justere knudepunkterne på dyngen. Hvis vi vil oprette maksimal heap, sammenlignes det aktuelle element med dets børn, og hvis værdien af ​​børn er større end det aktuelle element, udskiftes det med det største element i et venstre eller højre barn. Tilsvarende, hvis der skal oprettes min-bunke, udskiftes der med det mindste element i venstre eller højre barn. For eksempel er følgende vores input-array,

Vi kan betragte dette som et træ i stedet for et array. Det første element vil være rod, det andet vil være det venstre barn af rod, det tredje element vil være det rigtige barn af rod osv.

For at omdanne bunke til et træ skal du krydse træet i en nedad-op retning. Da bladknudepunkterne ikke har børn, lad os se nærmere på det næste niveau. dvs. er 5 og 7.

Vi kan begynde klokken 5, som det er til venstre. Her har 5 to børn: 9 og 4, hvor 9 er større end forældreknude 5. For at gøre forældrene større, bytter vi 5 og 9. Efter udskiftning vil træet være som vist nedenfor.

Lad os gå til det næste element 7, hvor 8 og 2 er børnene. I lighed med elementerne 9 og 4 vil 7 og 8 blive byttet som i nedenstående træ.

Endelig har 3 to børn-9 og 8, hvor 9 er større blandt børnene og rodfoden. Så udveksling af 3 og 9 vil blive gjort for at gøre roden større. Gentag processen, indtil der er dannet en gyldig bunke som vist nedenfor.

Algoritme til heap sortering i stigende rækkefølge

  1. Opret en Max Heap med inputdataene
  2. Udskift det sidste element med det største element i dyngen
  3. Hæv træet
  4. Gentag processen, indtil arrayet er sorteret

Algoritme til heap sortering i faldende rækkefølge

  1. Opret en Min Heap med inputdataene
  2. Udskift det sidste element med det mindste element i dyngen
  3. Hæv træet
  4. Gentag processen, indtil arrayet er sorteret

Lad os nu prøve at sortere den ovenfor opnåede Heap i stigende rækkefølge ved hjælp af den givne algoritme. Fjern først det største element. dvs. rod, og udskift det med det sidste element.

Heapify nu det dannede træ og indsæt det fjernede element i den sidste af arrayet som vist nedenfor

Fjern igen rodelementet, udskift det med det sidste element og Heapify det.

Sæt det fjernede element i den ledige position. Nu kan du se, at slutningen af ​​matrixen sorteres.

Fjern nu element 7 og udskift det med 2.

Hæv træet som vist nedenfor.

Gentag processen, indtil arrayet er sorteret. Fjernelse af element 5.

Heapifying træet.

Fjernelse af element 4.

Heapfying igen.

Til sidst vil der blive dannet et sorteret array som dette.

Eksempler på Implement Heap Sort i Java

Lad os nu 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));
)
)

Produktion

Konklusion

Heap Sort er en sorteringsteknik, der afhænger af strukturen i Binary Heap Data. Det ligner næsten valgssortering og bruger ikke separate arrays til sortering og dynge.

Anbefalet artikel

Dette har været en guide til Heap Sort i Java. Her diskuterer vi arbejdet, sortering af algoritme med stigende og faldende rækkefølge og eksempler med prøvekode. Du kan også gennemgå vores andre foreslåede artikler for at lære mere -

  1. JavaScript-matematikfunktioner
  2. Layout i Java
  3. Java Compilers
  4. Vejledning til fletningssortering i Java
  5. Guide til Heap Sort i C
  6. Eksempler på Heap Sort i C ++

Kategori:

Softwareudvikling