Úvod do triedenia haldy v jazyku Java

Heapsort v Jave je porovnávací spôsob triedenia, pri ktorom sa používa dátová štruktúra Binary Heap. Toto triedenie je takmer rovnaké ako pri výbere triedenia, kde bude vybraný najväčší prvok a miesta na konci a proces bude opakovaný pre všetky prvky. Aby sme porozumeli triedeniu haldy, pozrime sa, aké binárne haldy sú usporiadané v jazyku Java.

  • Stromová dátová štruktúra.
  • Kompletný binárny strom.
  • Môže mať až dve deti.
  • Hodnota v koreňovom uzle môže byť väčšia (Max Heap) alebo menšia (Min Heap)

Ako funguje triedenie haldy v jazyku Java?

Pred prechodom na algoritmus sa pozrime, čo je Heapify.

Heapify

Po vytvorení haldy so vstupnými údajmi nemusí byť vlastnosť haldy uspokojená. Aby sa to dosiahlo, na úpravu uzlov haldy sa použije funkcia nazývaná heapify. Ak chceme vytvoriť maximálnu hromadu, aktuálny prvok sa porovná s jeho deťmi a ak je hodnota detí vyššia ako aktuálny prvok, zámena sa uskutoční s najväčším prvkom v ľavom alebo pravom podriadenom. Podobne, ak je potrebné vytvoriť mincovňu, vykoná sa výmena s najmenším prvkom v ľavom alebo pravom dieťati. Napríklad, toto je naše vstupné pole,

Môžeme to považovať za strom namiesto poľa. Prvý prvok bude root, druhý bude ľavé dieťa root, tretí prvok bude pravé dieťa root a tak ďalej.

Ak chcete transformovať haldu na strom, posúvajte strom v smere zdola nahor. Pretože listové uzly nemajú deti, pozrime sa na ďalšiu úroveň. tj je 5 a 7.

Môžeme začať o piatej, ako je vľavo. Tu má 5 dve deti: 9 a 4, kde 9 je väčšie ako rodičovský uzol 5. Aby sme zväčšili rodičov, prehodíme 5 a 9. Po výmene bude strom taký, ako je znázornené nižšie.

Prejdime k ďalšiemu prvku 7, kde 8 a 2 sú deti. Podobne ako pri prvkoch 9 a 4, 7 a 8 sa budú zamieňať ako v spodnom strome.

Nakoniec, 3 majú dve deti - 9 a 8, z ktorých 9 je medzi deťmi a koreňmi väčšie. Preto sa uskutoční výmena 3 a 9, aby sa koreň zväčšil. Opakujte postup, kým sa nevytvorí platná halda, ako je to znázornené nižšie.

Algoritmus hromadenia haldy vo vzostupnom poradí

  1. Vytvorte Max Heap so vstupnými údajmi
  2. Nahraďte posledný prvok najväčším prvkom v halde
  3. Heapify Tree
  4. Opakujte tento postup, kým sa pole nezoradí

Algoritmus pre hromadenie haldy v zostupnom poradí

  1. Vytvorte minovú hromadu so vstupnými údajmi
  2. Nahraďte posledný prvok najmenším prvkom v halde
  3. Heapify Tree
  4. Opakujte tento postup, kým sa pole nezoradí

Skúsme teraz triediť vyššie získanú hromadu vo vzostupnom poradí pomocou daného algoritmu. Najskôr odstráňte najväčší prvok. tj root a nahradiť ho posledným prvkom.

Teraz vytvorte haldifikovaný strom a vložte odstránený prvok do poslednej z polí, ako je to znázornené nižšie

Opäť odstráňte koreňový prvok, nahraďte ho posledným prvkom a Heapify.

Vložte odstránený prvok do neobsadenej polohy. Teraz môžete vidieť, že koniec poľa sa triedi.

Teraz vyberte prvok 7 a vymeňte ho za 2.

Heapify strom, ako je uvedené nižšie.

Opakujte tento postup, kým sa pole nezoradí. Odstránenie prvku 5.

Halenie stromu.

Odstránenie prvku 4.

Heapfying znova.

Nakoniec sa vytvorí také zoradené pole.

Príklady implementácie triedenia haldy v jazyku Java

Teraz sa pozrime na zdrojový kód 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));
)
)

Výkon

záver

Usporiadanie haldy je technika triedenia, ktorá závisí od štruktúry binárnych údajov haldy. Je takmer podobný ako pri výbere triedenia a nepoužíva oddelené polia na triedenie a haldy.

Odporúčaný článok

Toto bol sprievodca Heap Sort in Java. Tu diskutujeme pracovný, triediaci algoritmus so vzostupným a zostupným poradím a príklady s ukážkovým kódom. Viac informácií nájdete aj v ďalších navrhovaných článkoch -

  1. Matematické funkcie JavaScriptu
  2. Rozloženie v Jave
  3. Kompilátory Java
  4. Sprievodca zlúčením zoradenia v jazyku Java
  5. Sprievodca hromadením haldy v C
  6. Príklady usporiadania haldy v C ++

Kategórie:

Vývoj softvéru