# Heap Sort in Java3 min read

In this post, we will learn how to implement Heap Sort in java.
Sorting Algorithm in java.

## Heap Sort Algorithm

Heap is a tree in heap sorting possess some specific properties whose value should be greater than or equal to that of the children node.
Heap sort is a comparison-based sorting algorithm and is also considered as the improved Selection sort. It is based on a Binary Heap data structure so to understand we must know two types of data structure:
Arrays and trees

### What is Binary heap?

Complete Binary tree:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Binary Heap:
A binary heap is a complete binary tree where the parent node is greater than its two children node.

Representation of Binary tree:
Considering the height of a tree be “h“, then:

• Index of left child = 2*(index of its parent)+1
• Index of right child = 2*(index of its parent)+2

### Types of heaps:

• Min heap
• Max heap

Min heap and max heap are the binary heap which represents the ordering of an array.

Min heap: In this binary heap, the value of the parent node is always greater than its child node.

Max heap: In this binary heap, the value of the parent node is always less than its child node.

Heap sorting algorithm for increasing order:

• First, create a max Heap from the input array.
• Replace the root element (which has the largest element) with the last element in the array. Then heapify the root of the tree.
• Now repeat the steps until all elements are sorted in an array.

Heap sorting algorithm for decreasing order.

• First, create a min Heap from the input array.
• Replace the root element (which has the smallest element) with the last element in the array. Then heapify the root of the tree.
• Now repeat the steps until all elements are sorted in an array.

## Time Complexity of Heap Sort:

Best case:  `0(nlogn)`
Average case:  `0(nlogn)`
Worst case:  `0(nlogn)`

## Java code for heap sort

The output of Heap sorting in Java: