Introducere la sortarea haldelor în Java

Heapsort în Java este o tehnică de sortare bazată pe comparație, unde se folosește structura de date Binary Heap. Această sortare este aproape aceeași cu cea a sortării de selecție, unde va fi selectat cel mai mare element și plasează la final și procesul va fi repetat pentru toate elementele. Pentru a înțelege Heap Sort, haideți să vedem ce sortare Bapă Heap în Java.

  • Structura de date bazată pe arbori.
  • Arbore binar complet.
  • Poate avea până la doi copii.
  • Valoarea din nodul rădăcină poate fi mai mare (Max Heap) sau mai mică (Min Heap)

Cum funcționează Heap Sort în Java?

Înainte de a trece la algoritm, să vedem ce este Heapify.

Heapify

După crearea unui heap cu datele de intrare, proprietatea heap nu poate fi satisfăcută. Pentru realizarea acesteia, o funcție numită heapify va fi utilizată pentru a regla nodurile grămei. Dacă dorim să creăm cantitate maximă, elementul curent va fi comparat cu copiii săi și dacă valoarea copiilor este mai mare decât elementul curent, schimbarea se va face cu cel mai mare element la un copil stâng sau drept. În mod similar, dacă este necesar să se creeze min-heap, schimbarea se va face cu cel mai mic element din copilul din stânga sau din dreapta. De exemplu, următorul este tabloul nostru de intrare,

Putem considera acest lucru ca un copac în locul unui Array. Primul element va fi rădăcina, al doilea va fi copilul rădăcină stâng, cel de-al treilea element va fi copilul rădăcină drept și așa mai departe.

Pentru a transforma grămada într-un copac, traversați arborele într-o direcție de jos în sus. Deoarece nodurile frunzelor nu au copii, să ne uităm la nivelul următor. adică este 5 și 7.

Putem începe la 5, deoarece este pe stânga. Aici, 5 are doi copii: 9 și 4, unde 9 este mai mare decât nodul părinte 5. Pentru a face părinții mai mari, vom schimba 5 și 9. După schimbare, arborele va fi așa cum se arată mai jos.

Să trecem la următorul element 7, unde 8 și 2 sunt copiii. Similar cu elementele 9 și 4, 7 și 8 vor fi schimbate ca în arborele de mai jos.

În cele din urmă, 3 are doi copii-9 și 8 unde 9 este mai mare în rândul copiilor și rădăcină. Deci, schimbarea a 3 și 9 se va face pentru a crește rădăcina. Repetați procesul până când se formează o grămadă validă, așa cum se arată mai jos.

Algoritmul pentru sortarea haldei în ordine crescătoare

  1. Creați un Heap Max cu datele de intrare
  2. Înlocuiți ultimul element cu cel mai mare element din grămadă
  3. Heapify Tree
  4. Repetați procesul până la sortarea tabloului

Algoritmul pentru sortarea haldei în ordine descrescătoare

  1. Creați un Heap Min cu datele de intrare
  2. Înlocuiți ultimul element cu cel mai mic element din grămadă
  3. Heapify Tree
  4. Repetați procesul până la sortarea tabloului

Acum, să încercăm să sortăm Heap-ul obținut mai sus în ordinea ascendentă folosind algoritmul dat. În primul rând, eliminați cel mai mare element. adică rădăcină și înlocuiește-l cu ultimul element.

Acum, heapificați arborele format și introduceți elementul eliminat în ultimul rând, după cum se arată mai jos

Din nou, scoateți elementul rădăcină, înlocuiți-l cu ultimul element și Heapify.

Introduceți elementul eliminat în poziția vacantă. Acum puteți vedea că sfârșitul tabloului este sortat.

Acum, Eliminați elementul 7 și înlocuiți-l cu 2.

Heapify arbore, după cum se arată mai jos.

Repetați procesul până la sortarea tabloului. Scoaterea elementului 5.

Heapifying the tree.

Scoaterea elementului 4.

Încălțăminte din nou.

În cele din urmă, va fi format un tablou sortat ca acesta.

Exemple pentru implementarea sortării heap în Java

Acum, să vedem codul sursă al Heap Sort în 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));
)
)

producție

Concluzie

Heap Sort este o tehnică de sortare care depinde de structura Binary Heap Data. Este aproape similară cu sortarea de selecție și nu folosește tablele separate pentru sortare și adunare.

Articol recomandat

Acesta a fost un ghid pentru Heap Sort în Java. Aici discutăm modul de lucru, Sortarea algoritmului cu ordine crescătoare și descendentă și exemple cu cod de probă. Puteți parcurge și alte articole sugerate pentru a afla mai multe -

  1. Funcții matematice JavaScript
  2. Aspect în Java
  3. Compilatoare Java
  4. Ghid pentru combinarea sortării în Java
  5. Ghid pentru sortarea haldei în C
  6. Exemple de sortare a haldei în C ++

Categorie:

Dezvoltare de software