Implementing Heap Sort in Java

In this tutorial, we will learn to implement heap sort in java.

A heap is a tree with some special properties, so the value of node should be greater than or equal to(less than or equal to in case of min heap) children of the node and tree should be a complete binary tree. Binary heaps are those heaps which can have up to 2 children.

A complete binary tree:




A complete binary tree is a binary tree whose leaves are at h or h-1 level (where h is the height of the tree).
Index of left child= 2*(index of its parent)+1
Index of right child= 2*(index of its parent)+2

Types of heaps

There are two types of heap:

  1. Max heap
  2. Min heap

Max heap : It is binary heap where value of node is greater than left and right child of the node.

Min heap : It is binary heap where value of node is lesser than left and right child of the node.

Once we have created a heap , it may not satisfy heap property. In order to make it heap again, we need to adjust locations of the heap and this process is known as heapifying the elements.
In order to create a max heap, we will compare current element with its children and find the maximum, if current element is not maximum then exchange it with maximum of left or right child.

Heap Sort in Java

public static void heapify_elements(int[] arr, int i,int size) { 
int left = 2*i+1;
int right = 2*i+2;
int max;
if(left <= size && arr[left] > arr[i]){
max=left;
} else {
max=i;
}

if(right <= size && arr[right] > arr[max]) {
max=right;
}

if(max!=i) {
swap(arr,i, max);
heapify_elements(arr, max,size);
}
}

Following are the steps to perform heap sort in Java:

  • Represent array as a complete binary tree.
    1. Left child will be at 2*i+1 th location
    2. Right child will be at 2*i+2 th location.
  • Building a heap:
    1. All the leaf nodes already satisfy heap property.
    2. Last leaf node will be present at (n-1)th location, so parent of it will be at (n-1)/2 th location, (n-1)/2 will be location of last non leaf node.
    3. Iterate over non leaf nodes and go on heapifying the elements.

 

  • After building a heap, max element will be at root of the heap. We will exchange it with (n-1)th location, so largest element will be at its place and then remove it from the heap by reducing size of n.
  • When you exchange largest element, it may disturb max heap property, so you need to again heapify it.
  • Once you do the above steps until no elements left in heap, you will get sorted array in the end.

Java Code:

import java.util.*;
public class Main {
 
   public static void build_heap(int []arr) {
      
    for(int i=(arr.length-1)/2; i>=0; i--){
     heapify_elements(arr,i,arr.length-1);
      }
   }
 
   public static void heapify_elements(int[] arr, int i,int size) { 
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
       max=left;
      } else {
       max=i;
      }
 
      if(right <= size && arr[right] > arr[max]) {
       max=right;
      }
      if(max!=i) {
         swap(arr,i, max);
         heapify_elements(arr, max,size);
      }
   }
 
   public static void swap(int[] array,int i, int k) {
        int t = array[i];
        array[i] = array[k];
        array[k] = t; 
   }
 
   public static int[] heapSort(int[] arr) {
     
      build_heap(arr);
      int size=arr.length-1;
      for(int i=size; i>0; i--) {
         swap(arr,0, i);
         size=size-1;
         heapify_elements(arr, 0,size);
      }
      return arr;
   }
 
   public static void main(String[] args) {
      int[] arr={1,10,15,23,3,5};
      System.out.println("Before Heap Sort : ");
      System.out.println(Arrays.toString(arr));
      arr=heapSort(arr);
      System.out.println("After Heap Sort : ");
      System.out.println(Arrays.toString(arr));
   }
}

Output:

Before Heap Sort : 
[1, 10, 15, 23, 3, 5]
After Heap Sort : 
[1, 3, 5, 10, 15, 23]

Also read,


Leave a Reply

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