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

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 | 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 (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:

Also, learn,**Bubble Sort in Java**