In this tutorial, we will learn how to implement Heap Sort in java. First, we will start by understanding the Heap Sort algorithm.

**Heap Sort Algorithm**

Heap is a tree in heap sorting that possesses some specific properties whose value should be greater than or equal to that of the children node.

Heapsort 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 heaps that represent 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.

**A 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.

**A 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.

Before we begin, you need to have an idea of the following:

## Time Complexity of Heap Sort:

**Best case:**`0(nlogn)`

**Average case:**`0(nlogn)`

**Worst case:**`0(nlogn)`

**Java Program to implement heap sort**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | import java.util.Arrays; public class HeapSortAlgo { public void sort(int arrA[]) { int size = arrA.length; // create heap for (int i = size / 2 - 1; i >= 0; i--) heapify(arrA, size, i); //Replacement of element for (int i = size - 1; i >= 0; i--) { //arrA[0] being max element int x = arrA[0]; arrA[0] = arrA[i]; arrA[i] = x; // call max heapify(arrA, i, 0); } } void heapify(int arrA[], int heapSize, int i) { // Initializing int largest = i; //Indexes int leftChild = 2 *i + 1; int rightChild = 2 *i + 2; // If left child is larger than root if (leftChild < heapSize && arrA[leftChild] > arrA[largest]) largest = leftChild; //if right child is larger than root if (rightChild < heapSize && arrA[rightChild] > arrA[largest]) largest = rightChild; // If root is not largest if (largest != i) { int swap = arrA[i]; arrA[i] = arrA[largest]; arrA[largest] = swap; // Recursive call heapify(arrA, heapSize, largest); } } public static void main(String args[]) { int arrA[] = { 6, 23, 9, 15, 4, 1, 11 }; System.out.println("Array before sorting: " + Arrays.toString(arrA)); HeapSortAlgo heapSort = new HeapSortAlgo(); heapSort.sort(arrA); System.out.println("Array after heap sort: " + Arrays.toString(arrA)); } } |

The **output **of Heap sorting in Java: