# 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.