Heap sort in Java

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 at Prepbytes.