Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Heap sort in Java

Last Updated on December 14, 2022 by Prepbytes

What is heap?

Heap is a special kind of complete binary tree in which the all node has a value greater (or smaller ) than all of its children .

A complete binary tree is a binary tree where all levels are completely filled except the last level which can be complete or incomplete . All nodes should be filled from left to right .

There are two types of heap , Min heap and Max heap . In Max heap all nodes have value greater than the children’s value whereas in Min heap all nodes have value smaller than the children’s value .

What is heap sort?

Heap sort is a sorting technique in which we use heap operations to sort the given array in ascending or descending order . For sorting in ascending order , we first create the max heap from the given array .
One by one we remove the max number (i.e root of heap ) to the end of the array and adjust other numbers to maintain heap property using heapify() . At the end , we have the array in ascending order .

heapify() : This is the most important operation in the heap sort algorithms . It ensures that heap property is maintained . Following is the process to heapify

  1. For heapify(i) , compare value of this node with left node (2 i+1) and right node (2 i+2) .
  2. If heap[i] >= max(heap[2 i+1] , heap[2 i+2] ) , then stop the process
  3. Else swap( heap[i] , heap[largest] ) , where ‘largest’ is child with larger value among left child and right child
  4. Call heapify(largest) .

Time complexity for the heapify method is O(logn).

Algorithm for heap sort :

  1. Create the max heap of given array
  2. Swap the root node of heap with the last node
  3. Decrease the size of heap and perform heapify
  4. Repeat 2-3 until the heap is empty .

Now let’s see the working of heap sort in detail by using an example.

Implementation of heap sort algorithm in java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class HeapSort{
    private int size;

    private void heapify(ArrayList<Integer> arr,int i){
        int next=i;
        if(2*i+1 < size && arr.get(2*i+1) > arr.get(next))next=2*i+1;
        if(2*i+2 < size && arr.get(2*i+2) > arr.get(next))next=2*i+2;
        
        if( next  == i)return;
        Collections.swap(arr,i,next);
        heapify(arr,next);
    }

    public void sort(ArrayList<Integer> arr){
        size = arr.size();
        for(int i= size-1; i>=0;i--){
            heapify(arr,i);
        }

        while(size > 0){
            Collections.swap(arr,0,size-1);
            size -- ;
            heapify(arr, 0);
        }
    }
}

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		ArrayList<Integer> arr = new ArrayList<Integer> ();
		arr.add(79);
		arr.add(71);
		arr.add(9);
		arr.add(11);
		arr.add(14);
		arr.add(76);
		arr.add(54);
		arr.add(32);
		
		System.out.println("before sorting :" + arr);
		new HeapSort().sort(arr);
		System.out.println("after sorting :" + arr);
		
	}
}

Time complexity for the above algorithm will be O(nlogn) in all cases . We are also not using any extra space as we are creating the heap using the given array itself , so space complexity will be O(1).

Similarly , we can create a Min heap for sorting the array in descending order . All we need to do is change the heapify method in HeapSort class .

This article tried to discuss Heap sort in Java. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

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