Inleiding tot Heap Sort in Java

Heapsort in Java is een op vergelijking gebaseerde sorteertechniek, waarbij datastructuur Binary Heap wordt gebruikt. Deze sortering is bijna hetzelfde als die van selectiesortering waarbij het grootste element wordt geselecteerd en aan het einde wordt geplaatst en het proces voor alle elementen wordt herhaald. Om Heap Sort te begrijpen, laten we eens kijken wat Binary Heap Sort in Java is.

  • Op boom gebaseerde gegevensstructuur.
  • Volledige binaire boom.
  • Het kan maximaal twee kinderen hebben.
  • De waarde in het hoofdknooppunt kan groter zijn (Max Heap) of Kleiner (Min Heap)

Hoe werkt Heap Sort in Java?

Voordat we naar het algoritme gaan, laten we kijken wat Heapify is.

Heapify

Nadat een heap is gemaakt met de invoergegevens, is mogelijk niet aan de heap-eigenschap voldaan. Om dit te bereiken, wordt een functie genaamd heapify gebruikt om de knooppunten van de heap aan te passen. Als we de maximale heap willen maken, wordt het huidige element vergeleken met de onderliggende elementen en als de waarde van de kinderen groter is dan het huidige element, wordt er gewisseld met het grootste element in een linker- of rechterkind. Evenzo, als min-heap moet worden gemaakt, zal ruilen worden gedaan met het kleinste element in het linker of rechter kind. Het volgende is bijvoorbeeld onze invoerarray,

We kunnen dit beschouwen als een boom in plaats van een array. Het eerste element zal root zijn, het tweede is het linkerkind van root, het derde element zal het rechterkind van root zijn enzovoort.

Om heap in een boom te transformeren, steekt u de boom in een bottom-up richting. Omdat de bladknopen geen kinderen hebben, laten we naar het volgende niveau kijken. dat wil zeggen 5 en 7.

We kunnen beginnen om 5 uur aan de linkerkant. Hier heeft 5 twee kinderen: 9 en 4, waarbij 9 groter is dan de ouderknoop 5. Om ouders groter te maken, zullen we 5 en 9 ruilen. Na het ruilen zal de boom zijn zoals hieronder getoond.

Laten we naar het volgende element 7 gaan waar 8 en 2 de kinderen zijn. Net als de elementen 9 en 4, zullen 7 en 8 worden verwisseld zoals in de onderstaande boom.

Ten slotte heeft 3 twee kinderen-9 en 8, waarbij 9 groter is bij de kinderen en de wortel. Dus, het ruilen van 3 en 9 zal gedaan worden om de wortel groter te maken. Herhaal het proces totdat een geldige heap is gevormd zoals hieronder wordt weergegeven.

Algoritme voor heap Sorteren in oplopende volgorde

  1. Maak een maximale hoop met de invoergegevens
  2. Vervang het laatste element door het grootste element in de heap
  3. Heapify the Tree
  4. Herhaal het proces totdat de array is gesorteerd

Algoritme voor heap Sorteren in aflopende volgorde

  1. Maak een Min Heap met de invoergegevens
  2. Vervang het laatste element door het kleinste element in de heap
  3. Heapify the Tree
  4. Herhaal het proces totdat de array is gesorteerd

Laten we nu proberen de hierboven verkregen Heap in stijgende volgorde te sorteren met behulp van het gegeven algoritme. Verwijder eerst het grootste element. dwz root en vervang het door het laatste element.

Heapify de gevormde boom en plaats het verwijderde element in de laatste van de array zoals hieronder getoond

Verwijder nogmaals het root-element, vervang het door het laatste element en heapify.

Plaats het verwijderde element in de lege positie. Nu kunt u zien dat het einde van de array wordt gesorteerd.

Verwijder nu element 7 en vervang het door 2.

Heapify the tree, zoals hieronder getoond.

Herhaal het proces totdat de array is gesorteerd. Element verwijderen 5.

De boom hopen.

Element verwijderen 4.

Heapfying opnieuw.

Eindelijk zal een gesorteerde reeks zoals deze worden gevormd.

Voorbeelden om Heap Sort in Java te implementeren

Laten we nu de broncode van Heap Sort in Java bekijken

//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));
)
)

uitgang

Conclusie

Heap Sort is een sorteertechniek die afhankelijk is van de binaire heap-gegevensstructuur. Het is bijna vergelijkbaar met selectiesortering en gebruikt geen afzonderlijke arrays voor sorteren en heap.

Aanbevolen artikel

Dit is een gids voor Heap Sort in Java. Hier bespreken we de werkende, sorteeralgoritme met oplopende en aflopende volgorde en voorbeelden met voorbeeldcode. U kunt ook onze andere voorgestelde artikelen doornemen voor meer informatie -

  1. JavaScript-wiskundige functies
  2. Indeling in Java
  3. Java-compilers
  4. Gids voor samenvoegen sorteren in Java
  5. Gids voor Heap Sort in C
  6. Voorbeelden van heap-sortering in C ++

Categorie:

Software ontwikkeling