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);
        }
    }
}

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.

Program for Heap Sort in Java

1 thought on “Heap Sort in Java”

Leave a Comment Cancel Reply

Program for Heap Sort in Java

Related Posts

1 thought on “Heap Sort in Java”

Leave a Comment Cancel Reply