Sissejuhatus Java-s sorteerimisse

Heapsort Java-s on võrdluspõhine sorteerimistehnika, kus kasutatakse andmestruktuuri Binary Heap. See sorteerimine on peaaegu sama, mis sortimisvalikul, kus valitakse suurim element ja paigutatakse lõpuks lõppu ning protsessi korratakse kõigi elementide puhul. Heap-sortimise mõistmiseks vaatame, milline on Java binaarne hunnik.

  • Puupõhine andmestruktuur.
  • Täielik kahendpuu.
  • Selles võib olla kuni kaks last.
  • Väärtus juursõlmes võib olla suurem (Max Heap) või väiksem (Min Heap)

Kuidas Heap Sort Java töötab?

Enne algoritmi juurde liikumist vaatame, mis on Heapify.

Heapify

Pärast hunniku loomist sisendandmetega ei pruugi hunniku atribuut olla rahul. Selle saavutamiseks kasutatakse hunniku sõlmede reguleerimiseks funktsiooni nimega heapify. Kui tahame luua maksimaalse hunniku, võrreldakse praegust elementi selle lastega ja kui laste väärtus on suurem kui praegune element, toimub vahetus vasaku või parema lapse suurima elemendiga. Samamoodi, kui on vaja luua min-hunnik, toimub vahetus väikseima elemendiga vasakus või paremas lapses. Näiteks järgmine on meie sisendmassiiv,

Võime seda pidada massiivi asemel puuks. Esimene element on juur, teine ​​on juure vasak laps, kolmas element on juure parem laps jne.

Hunniku muutmiseks puuks liikuge puu alt ülespoole. Kuna lehesõlmedel pole lapsi, uurime järgmist taset. st on 5 ja 7.

Saame alustada kell 5, kuna see on vasakul. Siin on 5-l kaks last: 9 ja 4, kus 9 on suurem kui põhisõlm 5. Vanemate suuremaks muutmiseks vahetame 5 ja 9. Pärast vahetamist on puu selline, nagu allpool näidatud.

Liigume järgmise elemendi 7 juurde, kus 8 ja 2 on lapsed. Sarnaselt elementidega 9 ja 4, 7 ja 8 vahetatakse nagu allpool olevas puus.

Lõpuks on 3-l kaks last-9 ja 8, kus 9 on laste seas suurem ja juur. Niisiis vahetatakse 3 ja 9, et juur oleks suurem. Korrake toimingut, kuni moodustub kehtiv hunnik, nagu allpool näidatud.

Hunnikute sortimise algoritm kasvavas järjekorras

  1. Looge sisendandmetega Max Heap
  2. Asendage viimane element hunniku suurima elemendiga
  3. Korista puu täis
  4. Korda protseduuri, kuni massiiv on sorteeritud

Hunnikute sortimise algoritm kahanevas järjekorras

  1. Looge sisendandmetega Min Heap
  2. Asendage viimane element hunniku väikseima elemendiga
  3. Korista puu täis
  4. Korda protseduuri, kuni massiiv on sorteeritud

Proovime nüüd saadud algoritmi abil järjestada ülalnimetatud Hunnik kasvavas järjekorras. Esiteks eemaldage suurim element. st juur ja asenda see viimase elemendiga.

Nüüd heparifitseerige moodustatud puu ja sisestage eemaldatud element massiivi viimasesse, nagu allpool näidatud

Jällegi eemaldage juurelement, asendage see viimase elemendiga ja Parendage see.

Pange eemaldatud element vabale kohale. Nüüd näete, et massiivi lõppu sorteeritakse.

Nüüd eemaldage element 7 ja asendage see 2-ga.

Kõrgutage puu, nagu allpool näidatud.

Korda protseduuri, kuni massiiv on sorteeritud. Elemendi 5 eemaldamine.

Puu parandamine.

Elemendi 4 eemaldamine.

Jälle raskekujuline.

Lõpuks moodustatakse selline sorteeritud massiiv.

Näited hunnikute sorteerimise rakendamiseks Java-s

Vaatame nüüd Java-s Heap Sort lähtekoodi

//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äljund

Järeldus

Heap Sort on sorteerimistehnika, mis sõltub binaarsete hunnikute andmete struktuurist. See sarnaneb peaaegu valiku sortimisega ja ei kasuta sortimiseks ja hunnikuks eraldi massiive.

Soovitatav artikkel

See on Java-s Heap Sortimise teejuht. Siin käsitleme toimivat, sortimisalgoritmi tõusvas ja langevas järjekorras ning näiteid koos näidiskoodiga. Lisateavet leiate ka meie muudest soovitatud artiklitest -

  1. JavaScripti matemaatikafunktsioonid
  2. Paigutus Java-s
  3. Java kompilaatorid
  4. Juhend Java-s sortimise ühendamiseks
  5. Juhend hunnikusse sortimiseks C-s
  6. Näited hunniku sortimisest C ++

Kategooria:

Tarkvaraarendus