How to Implement Heap Sort using Java

Hey Folks,
I am up with a new tutorial of data structures in Java. So in this tutorial, we will learn how to Implement Heap Sort using Java. Sorting is a very important step during competitive programming. It is the determining step in defining time complexity.

So let’s start with our tutorial. It is like selection sort, in it first we find the maximum element and place it at the end. We first build a heap with a given array. We can call it a max heap. It means that the largest element will be at the root position.

Code to Implement Heap Sort using Java

We repeatedly perform the heapify function. It puts the largest element at the root and rearranges our binary tree. Heap sort time complexity is better than any sorting algorithm. For sorting the if performs recursive calling of the heapify function.

Creating HeapSort.java file

public class HeapSort 
{
  public void sort(int arr[])
  {
     	int n=arr.length;
    int i;
    for(i=n/2-1;i>=0;i--)
    {
      heapify(arr,n,i);
    }
    for(i=n-1;i>=0;i--)
    {
      int temp=arr[0];
      arr[0]=arr[i];
      arr[i]=temp;
      heapify(arr,i,0);
    }
  }
  public void heapify(int arr[],int n,int i)
  {
    int largest=i;
    int l=2*i+1;
    int r=2*i +2;
    if(l<n && arr[l]>arr[largest])
      largest=l;
    if(r<n && arr[r]>arr[largest])
      largest=r;
    if(largest!=i)
    {
      int swap=arr[i];
      arr[i]=arr[largest];
      arr[largest]=swap;
      heapify(arr,n,largest);
    }
  }
  public void print(int arr[]) 
    { 
        for (int i = 0; i < arr.length / 2; i++) { 
            System.out.print(" PARENT : " + arr[i] + " LEFT CHILD : " + 
                      arr[2 * i+1] + " RIGHT CHILD :" + arr[2 * i + 2]); 
            System.out.println(); 
        } 
    } 
  public void printArray(int arr[])
  {	
    int n=arr.length;
    
    for(int i=0;i<n;i++)
    {
      System.out.println(arr[i] +" ");
    }
    
  }
}

Creating Runner.java file

public class Runner 
{
  public static void main(String[] args) 
  {
    HeapSort hs=new HeapSort();
    int arr[]= {12,11,13,5,6,7,145};
  //	int n=arr.length;
    hs.sort(arr);
    System.out.println("Sorted Array");
    hs.printArray(arr);
  }

}

 

We remove the root element because of it the largest. And we replace it with the last element in the binary heap tree. So after replacing, we need to heapify again to bring the largest element to the root position.

In this way, we replace and remove element repeatedly until the size of our tree is greater than one. Our first task is to create max heap. To make binary we follow a procedure. Place a random element at the root and if the next element is greater than root place it to the right.

If the next element is less than the root element place it to left. Repeat the procedure to make a binary tree. Then get max heap by recursively calling heapify function. In Runner file, we have created an object of HeapSort type named hs.
And to sort our array we use a standard format of java objectName.functionName() to call that function from the previous file.

I hope you understood the code well. Feel free to ask our doubts in the comment section below.

You may also read,

 

Leave a Reply

Your email address will not be published. Required fields are marked *