In this article we will discuss about **HeapShort algorithm**, Heap sort is a **Heap data structure** based comparison
sorting technique where we first find the maximum element and place the maximum element at the end. We repeat the same process for
remaining elements.

A **Binary Heap** is a **Complete Binary Tree**where items are stored in an order such that the value of each parent node
is either greater or smaller than the values of its two children nodes. The former is called as max heap and the latter is
called min heap. The heap can be represented by binary tree or array.

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.

As Binary Heap is a Complete Binary Tree, it can be easily represented as an array. If the parent node is stored at
index **"i"**, the left child can be calculated by **2 * i + 1** and right child by **2 * i + 2**.

The algorithm has two parts, one is to heapify the array and second part is to take last element as sorted and
repeat heapify for remaining array. In heapify we starts from the last non-leaf node (calculated by **n/2 -1**)
and check if the heap satisfies (maxHeap or minHeap) properties if not we keep on swapping elements until the targeted part
of array (heap) is heapified, we do it recursively.

package com.cd.array.sort; import java.util.Arrays; import java.util.stream.Collectors; public class HeapSort { private static int[] arr1 = {4, 10, 3, 5, 1}; private static int[] arr2 = {12, 11, 13, 5, 6, 7}; private static void sort(int[] arr, int n) { while (n > 0) { int lastNonLeaf = (n / 2) - 1; for (int i = lastNonLeaf; i >= 0; i--) maxHeapify(arr, i, n); swap(0, n - 1, arr); n--; } } private static void maxHeapify(int[] arr, int elementIndex, int n) { if (elementIndex > n - 1) return; int leftIndex = (elementIndex * 2) + 1; int rightIndex = (elementIndex * 2) + 2; if (leftIndex < n && arr[leftIndex] > arr[elementIndex]) { swap(elementIndex, leftIndex, arr); maxHeapify(arr, leftIndex, n); } if (rightIndex < n && arr[rightIndex] > arr[elementIndex]) { swap(elementIndex, rightIndex, arr); maxHeapify(arr, rightIndex, n); } } private static void swap(int i, int j, int arr[]) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } private static String print(int[] arr) { return Arrays.stream(arr).mapToObj(Integer::toString) .collect(Collectors.joining(", ")); } public static void main(String[] args) { System.out.println("Unsoretd array: " + print(arr1)); sort(arr1, arr1.length); System.out.println("Unsoretd array: " + print(arr1)); System.out.println(); System.out.println("Unsoretd array: " + print(arr2)); sort(arr2, arr2.length); System.out.println("Unsoretd array: " + print(arr2)); } }

**Output:**Output of above code will be something like this:

```
Unsoretd array: 4, 10, 3, 5, 1
Unsoretd array: 1, 3, 4, 5, 10
Unsoretd array: 12, 11, 13, 5, 6, 7
Unsoretd array: 5, 6, 7, 11, 12, 13
```

Heap sort is an

**in-place, not stable**sorting algorithm having a time complexity is

**O(nLogn)**, although there are ways to make heap sort stable.