Bevezetés a Java sorba rendezéséhez
A Heapsort a Java-ban egy összehasonlítási alapú válogatási technika, ahol az adatszerkezet Binary Heap kerül felhasználásra. Ez a szortírozás majdnem megegyezik a szelekciós válogatással, ahol a legnagyobb elem kerül kiválasztásra, és a végén elhelyezkedik, és a folyamat megismétlődik az összes elemnél. A Heap Sort megértése érdekében nézzük meg, hogy milyen bináris Heap Sort a Java.
- Faalapú adatstruktúra.
- Teljes bináris fa.
- Legfeljebb két gyermek lehet.
- Az érték a gyökércsomópontban nagyobb lehet (Max Heap) vagy kisebb (Min Heap)
Hogyan működik a Heap Sort Java?
Mielőtt továbblépnénk az algoritmushoz, nézzük meg, mi a Heapify.
Heapify
Miután létrehozott egy halom a bemeneti adatokkal, előfordulhat, hogy a halom tulajdonsága nem teljesül. Ennek elérése érdekében a heapify nevû funkciót használják a halom csomópontjainak beállítására. Ha max halomot akarunk létrehozni, akkor az aktuális elemet összehasonlítjuk a gyermekeivel, és ha a gyermekek értéke nagyobb, mint az aktuális elem, akkor a csere a bal vagy a jobb gyermek legnagyobb elemével történik. Hasonlóképpen, ha min-halomot kell létrehozni, akkor a csere a bal vagy a jobb gyermek legkisebb elemével történik. Például, a következő a bemeneti tömbünk,
Ezt tömb helyett fának tekinthetjük. Az első elem gyökér lesz, a második a gyökér bal gyermeke, a harmadik elem a gyökér jobb gyermeke stb.
Annak érdekében, hogy a halom fává alakuljon, mozgassa a fát alulról felfelé. Mivel a levélcsomóknak nincsenek gyermekeik, vizsgáljuk meg a következő szintet. azaz 5 és 7.
5-kor kezdhetjük, mivel balra van. Itt az 5-nek két gyermeke van: 9-ben és 4-ben, ahol 9 nagyobb, mint az 5 szülőcsomópont. Ahhoz, hogy a szülők nagyobbak legyenek, az 5-et és 9-et cseréljük. A csere után a fa az alább látható.
Menjünk a következő 7 elemhez, ahol 8 és 2 a gyerekek. A 9-es és a 4-es elemhez hasonlóan a 7-es és a 8-as elem cseréje is megtörténik, mint az alábbi fában.
Végül, 3-nak két gyermeke van - 9 és 8, ahol a 9 nagyobb a gyermekek között és a gyökér. Tehát a 3 és a 9 cseréje megtörténik, hogy nagyobb legyen a gyökér. Ismételje meg a folyamatot, amíg érvényes kupac képződik, az alább látható módon.
A halom növekvő sorrendjének algoritmusa
- Hozzon létre egy Max Heap-t a bemeneti adatokkal
- Cserélje le az utolsó elemet a halom legnagyobb elemére
- Felfújja a fa
- Ismételje meg a folyamatot, amíg a tömb rendezve van
A halom sorrendjének algoritmusa csökkenő sorrendben
- Hozzon létre egy Min Heap-t a bemeneti adatokkal
- Cserélje le az utolsó elemet a halom legkisebb elemére
- Felfújja a fa
- Ismételje meg a folyamatot, amíg a tömb rendezve van
Most próbáljuk meg rendezni a fentebb kapott Heap-et növekvő sorrendben az adott algoritmus segítségével. Először távolítsa el a legnagyobb elemet. azaz gyökér, és cserélje le az utolsó elemre.
Most töltsük fel a képződött fa faját, és helyezze be az eltávolított elemet a tömb utolsó részébe, az alább látható módon
Ismét távolítsa el a gyökér elemet, cserélje le az utolsó elemre, és fejlessze fel.
Helyezze az eltávolított elemet üres helyre. Most láthatja, hogy a tömb vége rendezésre kerül.
Most távolítsa el a 7 elemet, és cserélje ki 2-re.
Húzza meg a fát az alább látható módon.
Ismételje meg a folyamatot, amíg a tömb rendezve van. 5. elem eltávolítása.
A fa megnöveli.
4. elem eltávolítása.
Ismét melegítés.
Végül egy ilyen rendezett tömb jön létre.
Példák a halomrendezés végrehajtására Java-ban
Most nézzük meg a Heap Sort forráskódját a Java-ban
//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));
)
)
Kimenet
Következtetés
A Heap Sort egy olyan válogatási technika, amely a bináris Heap Data struktúrától függ. Ez majdnem hasonló a válogatáshoz, és nem használ külön tömböket a válogatáshoz és a halomhoz.
Ajánlott cikk
Ez egy útmutató a Heap Sort használatához Java-ban. Itt tárgyaljuk a működő, rendezési algoritmust növekvő és csökkenő sorrenddel, valamint példákat a mintakóddal. A további javasolt cikkeken keresztül további információkat is megtudhat -
- JavaScript matematikai funkciók
- Elrendezés Java-ban
- Java fordító
- Útmutató a Java böngészéshez történő rendezéshez
- Útmutató a halom rendezéséhez C-ben
- Példák a halomfajtára C ++-ban