Heap Sort in Java

Here you will get program for heap sort in java.

Heap sort is a sorting algorithm that uses heap data structure. Its best, worst and average time complexity is O (n log n).

How heap sort algorithm works?

• First we make max heap from given set of elements. In max heap each parent node is greater than or equal to its left and right child.
• Now first node is swapped by last node and size of heap is reduced by 1. After each swap we check the heap satisfies max heap property or not.
• The above step is repeated until the size of heap is more than 1.

Program for Heap Sort in Java

package com;

import java.util.Scanner;

public class HeapSortJava
{
    public static void main(String args[])
    {
    	int n, a[];
    	Scanner sc = new Scanner(System.in);
    	System.out.println("Enter number of elements:");
    	
    	n = sc.nextInt();
    	a = new int[n];

    	System.out.println("\nEnter the elements:");
    	for(int i = 0; i < n; ++i)
    		a[i] = sc.nextInt();
    	
    	new HeapSortJava().sort(a);
 
        System.out.println("\nSorted array is:");
        for(int i = 0; i < n; ++i)
        	System.out.print(a[i]+" ");
        
        sc.close();
    }
    
    public void sort(int a[])
    {
        int len = a.length - 1;
 
        for (int i = len/2; i >= 0; i--)
            heapify(a, len, i);
 
        for (int i = len; i >= 0; i--)
        {
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
 
            heapify(a, i, 0);
        }
    }
 
    void heapify(int a[], int n, int i)
    {
        int max = i;
        int l = 2*i + 1;
        int r = 2*i + 2;
 
        if (l < n && a[l] > a[max])
            max = l;
 
        if (r < n && a[r] > a[max])
            max = r;
 
        if (max != i)
        {
            int temp = a[i];
            a[i] = a[max];
            a[max] = temp;
 
            heapify(a, n, max);
        }
    }
}

Output

Enter number of elements:
6

Enter the elements:
12 56 34 2 10 10

Sorted array is:
2 10 10 12 34 56

You can watch below video to learn about heap sort algorithm.

Comment below if you have any doubts related to above program for heap sort in java.