Introduktion till Heap Sort In Java

Heapsort i Java är en jämförelsebaserad sorteringsteknik, där datastruktur Binary Heap används. Denna sortering är nästan densamma som den för urvalsorter där det största elementet kommer att väljas och placeras i slutet och processen kommer att upprepas för alla element. För att förstå Heap Sort, låt oss se vad Binary Heap Sort i Java.

  • Trädbaserad datastruktur.
  • Komplett binärt träd.
  • Det kan ha upp till två barn.
  • Värdet i rotnoden kan vara större (Max Heap) eller Mindre (Min Heap)

Hur fungerar Heap Sort i Java?

Innan vi går över till algoritmen, låt oss se vad som är Heapify.

Heapify

När en hög har skapats med inmatningsdata kanske heap-egenskapen inte är nöjd. För att uppnå det kommer en funktion som kallas heapify att användas för att justera hopens noder. Om vi ​​vill skapa maxheap, kommer det nuvarande elementet att jämföras med dess barn och om värdet på barn är större än det nuvarande elementet, byts det med det största elementet i ett vänster- eller högerbarn. På samma sätt, om min-heap behöver skapas, kommer byte att göras med det minsta elementet i vänster eller höger barn. Till exempel är följande vårt inmatningsfält,

Vi kan betrakta detta som ett träd istället för en array. Det första elementet kommer att vara rot, det andra kommer att vara det vänstra barnet till roten, det tredje elementet kommer att vara det högra barnet till roten och så vidare.

För att förvandla högen till ett träd, korsa trädet i en ner-upp-riktning. Eftersom bladnoderna inte har barn, låt oss undersöka nästa nivå. dvs är 5 och 7.

Vi kan börja klockan 5 när det är till vänster. Här har 5 två barn: 9 och 4, där 9 är större än föräldernoden 5. För att göra föräldrarna större byter vi 5 och 9. Efter byte kommer trädet att visas som nedan.

Låt oss gå till nästa element 7 där 8 och 2 är barnen. Liknande elementen 9 och 4 kommer 7 och 8 att bytas ut som i nedanstående träd.

Slutligen har 3 två barn-9 och 8 där 9 är större bland barnen och roten. Så, byte av 3 och 9 kommer att göras för att göra roten större. Upprepa processen tills en giltig hög bildas som visas nedan.

Algoritm för hög sortering i stigande ordning

  1. Skapa en Max Heap med inmatningsdata
  2. Byt ut det sista elementet med det största elementet i högen
  3. Heapify the Tree
  4. Upprepa processen tills matrisen är sorterad

Algoritm för hög sortering i fallande ordning

  1. Skapa en Min Heap med inmatningsdata
  2. Byt ut det sista elementet med det minsta elementet i högen
  3. Heapify the Tree
  4. Upprepa processen tills matrisen är sorterad

Låt oss nu försöka sortera den ovan erhållna Heap i stigande ordning med den angivna algoritmen. Ta först bort det största elementet. dvs root och ersätt det med det sista elementet.

Heapify nu trädet och sätt in det borttagna elementet i den sista av matrisen som visas nedan

Återigen, ta bort rotelementet, ersätt det med det sista elementet och Heapify det.

Sätt i det borttagna elementet i det lediga läget. Nu kan du se att slutet på matrisen sorteras.

Ta bort element 7 och ersätt det med 2.

Högen trädet, som visas nedan.

Upprepa processen tills matrisen är sorterad. Ta bort element 5.

Höger trädet.

Ta bort element 4.

Heapfying igen.

Till sist kommer en sorterad grupp som denna att bildas.

Exempel på Implement Heap Sort i Java

Låt oss nu se källkoden för Heap Sort i 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));
)
)

Produktion

Slutsats

Heap Sort är en sorteringsteknik som beror på strukturen för Binary Heap Data. Det liknar nästan sorteringssortering och använder inte separata matriser för sortering och hög.

Rekommenderad artikel

Detta har varit en guide till Heap Sort i Java. Här diskuterar vi det fungerande, sortera algoritmen med stigande och fallande ordning och exempel med exempelkod. Du kan också gå igenom våra andra föreslagna artiklar för att lära dig mer -

  1. JavaScript-matematiska funktioner
  2. Layout i Java
  3. Java-kompilatorer
  4. Guide för att slå samman sortering i Java
  5. Guide to Heap Sort in C
  6. Exempel på Heap Sort i C ++

Kategori:

Mjukvaruutveckling