Úvod do haldy v Java

Heapsort v Javě je metoda třídění založená na porovnání, kde se používá datová struktura Binary Heap. Toto třídění je téměř stejné jako u třídění výběru, kde bude vybrán největší prvek a místa na konci a proces bude opakován pro všechny prvky. Abychom pochopili Heap Sort, podívejme se, co Binary Heap Sort v Java.

  • Stromová datová struktura.
  • Kompletní binární strom.
  • Může mít až dvě děti.
  • Hodnota v kořenovém uzlu může být větší (Max Heap) nebo menší (Min Heap)

Jak funguje Heap Sort v Javě?

Před přechodem na algoritmus se podívejme, co je Heapify.

Heapify

Po vytvoření haldy se vstupními daty nemusí být vlastnost haldy uspokojena. Aby se toho dosáhlo, použije se funkce nazvaná heapify k úpravě uzlů haldy. Pokud chceme vytvořit maximální hromadu, bude aktuální prvek porovnán s jeho podřízenými a pokud je hodnota dětí větší než aktuální prvek, bude nahrazení provedeno s největším prvkem v levém nebo pravém podřízeném. Podobně, pokud je třeba vytvořit mincovnu, provede se výměna s nejmenším prvkem v levém nebo pravém dítěti. Příklad: Toto je naše vstupní pole,

Můžeme to považovat za strom místo Array. První prvek bude root, druhý bude levé dítě root, třetí prvek bude pravé dítě root a tak dále.

Za účelem transformace haldy na strom procházejte stromem směrem zdola nahoru. Protože listové uzly nemají děti, podívejme se na další úroveň. tj. je 5 a 7.

Můžeme začít v 5, jak je vlevo. Zde má 5 dvě děti: 9 a 4, kde 9 je větší než rodičovský uzel 5. Aby se rodiče zvětšili, vyměníme 5 a 9. Po výměně bude strom zobrazen níže.

Přejdeme k dalšímu prvku 7, kde 8 a 2 jsou děti. Podobně jako u prvků 9 a 4, 7 a 8 budou zaměněny jako ve stromu níže.

Konečně, 3 mají dvě děti - 9 a 8, kde 9 je větší mezi dětmi a kořeny. Zaměníme 3 a 9, aby se kořen zvětšil. Postup opakujte, dokud se nevytvoří platná halda, jak je ukázáno níže.

Algoritmus pro hromadění haldy ve vzestupném pořadí

  1. Vytvořte Max Heap se vstupními daty
  2. Nahraďte poslední prvek největším prvkem v haldě
  3. Vymažte strom
  4. Tento postup opakujte, dokud nebude pole seřazeno

Algoritmus pro řazení haldy v sestupném pořadí

  1. Vytvořte Min Haldu se vstupními daty
  2. Nahraďte poslední prvek nejmenším prvkem v haldě
  3. Vymažte strom
  4. Tento postup opakujte, dokud nebude pole seřazeno

Nyní zkusme seřadit výše získanou hromadu ve vzestupném pořadí pomocí daného algoritmu. Nejprve odeberte největší prvek. tj. root a nahraďte jej posledním prvkem.

Nyní vytvořte vytvořený strom a vložte odebraný prvek do posledního pole, jak je ukázáno níže

Opět vyjměte kořenový prvek, nahraďte jej posledním a Heapify.

Vložte odebraný prvek do volné pozice. Nyní můžete vidět, že konec pole se třídí.

Nyní vyjměte prvek 7 a nahraďte jej 2.

Vymažte strom, jak je znázorněno níže.

Tento postup opakujte, dokud nebude pole seřazeno. Odstranění prvku 5.

Heapifying strom.

Odstranění prvku 4.

Heapfying znovu.

Nakonec se vytvoří takto seřazené pole.

Příklady implementace řazení haldy v Javě

Nyní se podívejme na zdrojový kód Heap Sort v Javě

//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ýstup

Závěr

Hromadné třídění je technika třídění, která závisí na struktuře dat binární haldy. Je téměř podobný výběrovému třídění a pro třídění a haldu nepoužívá samostatná pole.

Doporučený článek

Toto byl průvodce Heap Sort in Java. Zde diskutujeme pracovní, třídicí algoritmus s vzestupným a sestupným řádem a příklady s ukázkovým kódem. Další informace naleznete také v dalších navrhovaných článcích -

  1. Matematické funkce JavaScriptu
  2. Rozložení v Javě
  3. Kompilátory Java
  4. Průvodce sloučením třídění v Javě
  5. Průvodce hromadou haldy v C
  6. Příklady řazení haldy v C ++

Kategorie:

Vývoj softwaru