Uvod v razvrščanje kopice na Javi

Heapsort na Javi je primerjalna tehnika sortiranja, kjer se uporablja struktura podatkov Binary Heap. To razvrščanje je skoraj enako kot izbira, kjer bo izbran največji element in postavljen na koncu, postopek pa se bo ponovil za vse elemente. Da bi razumeli razvrščanje Heap, si oglejmo, kaj Bina razvrsti v javi.

  • Drevesna struktura podatkov.
  • Popolno Binarno drevo.
  • Lahko ima do dva otroka.
  • Vrednost v korenskem vozlišču je lahko večja (Max Heap) ali Manjša (Min Heap)

Kako Heap Sort deluje na Javi?

Preden se pomaknemo na algoritem, poglejmo, kaj je Heapify.

Pozdravite

Ko ustvarite kopico z vhodnimi podatki, lastnost kopice morda ne bo izpolnjena. Da bi ga dosegli, se bo za nastavitev vozlišč kopice uporabila funkcija imenovana heapify. Če želimo ustvariti max heap, bomo trenutni element primerjali z njegovimi otroki in če je vrednost otrok večja od trenutnega elementa, bomo zamenjali z največjim elementom v levem ali desnem otroku. Podobno, če je treba ustvariti min-heap, bo zamenjava izvedena z najmanjšim elementom pri levem ali desnem otroku. Na primer: Naslednji je naš vhodni niz,

To lahko smatramo kot drevo namesto matrike. Prvi element bo koren, drugi bo levi otrok korenine, tretji element bo pravi otrok korena in tako naprej.

Da bi kup preoblikovali v drevo, ga potegnite v smeri od spodaj navzgor. Ker listna vozlišča nimajo otrok, poglejmo v naslednjo stopnjo. to je 5 in 7.

Začnemo lahko ob 5, kot je na levi strani. Tukaj ima 5 dva otroka: 9 in 4, kjer je 9 večje od matičnega vozlišča 5. Da bi starši postali večji, bomo zamenjali 5 in 9. Po zamenjavi bo drevo, kot je prikazano spodaj.

Pojdimo na naslednji element 7, kjer sta 8 in 2 otrok. Podobno kot pri elementih 9 in 4, 7 in 8 se bodo zamenjali kot v spodnjem drevesu.

Končno, 3 ima dva otroka - 9 in 8, kjer je 9 več med otroki in koreninami. Torej, zamenjava 3 in 9 bo izvedena, da bo koren večji. Postopek ponavljajte, dokler ni oblikovan veljaven kup, kot je prikazano spodaj.

Algoritem za grozd Razvrsti po naraščajočem vrstnem redu

  1. Ustvari Max Heap z vhodnimi podatki
  2. Zadnji element zamenjajte z največjim elementom v kopici
  3. Dvigni drevo
  4. Postopek ponavljajte, dokler se matrika ne razvrsti

Algoritem za grozd Razvrsti po padajočem vrstnem redu

  1. Ustvari Min Heap z vhodnimi podatki
  2. Zadnji element zamenjajte z najmanjšim elementom v gomili
  3. Dvigni drevo
  4. Postopek ponavljajte, dokler se matrika ne razvrsti

Zdaj poskusimo razvrstiti zgoraj pridobljeno Heap v naraščajočem vrstnem redu z uporabo danega algoritma. Najprej odstranite največji element. koren in ga nadomestite z zadnjim elementom.

Zdaj segrejte oblikovano drevo in vstavite odstranjeni element v zadnji niz matrike, kot je prikazano spodaj

Ponovno odstranite korenski element, ga nadomestite z zadnjim elementom in ga natrenirajte.

Odstranjeni element vstavite v prosto mesto. Zdaj lahko vidite, da je konec matrice razvrščen.

Zdaj odstranite element 7 in ga nadomestite z 2.

Dvignite drevo, kot je prikazano spodaj.

Postopek ponavljajte, dokler se matrika ne razvrsti. Odstranjevanje elementa 5.

Ogrevanje drevesa.

Odstranjevanje elementa 4.

Spet greje.

Končno bo oblikovan takšen razvrščen niz.

Primeri za izvajanje razvrščanja heap v Javi

Zdaj pa si oglejmo izvirno kodo razvrstitve v Javi

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

Izhod

Zaključek

Heap Sort je tehnika razvrščanja, ki je odvisna od strukture Binary Heap Data. Je skoraj podobna selekcijski vrsti in ne uporablja ločenih nizov za razvrščanje in kopico.

Priporočeni članek

To je vodnik za razvrščanje heap v Javi. Tukaj razpravljamo o delu, sortiranju algoritma z naraščajočim in padajočim vrstnim redom ter primere z vzorčno kodo. Če želite izvedeti več, lahko preberete tudi druge naše predlagane članke -

  1. JavaScript matematične funkcije
  2. Postavitev v Javi
  3. Kompilatorji Java
  4. Vodnik za združevanje v Java
  5. Vodnik po razvrščanju gomile v C
  6. Primeri razvrščanja po kupu v C ++

Kategorija:

Razvoj programske opreme