**What is Heap Sort??**

- Heap sort is comparison based sorting algorithm.
- Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region.
- The improvement from selection sort is to use Heap Data Structure instead of using linear search algorithm to reduce of the time complexity.

**Pre-requisite:**

Binary Heap (min and max heap)

**What is Binary Heap??**

Heap is a tree based data structure which satisfies the two properties

**Shape Property**: Heap data structure is always a Complete Binary Tree. The Complete Binary tree is a binary tree which is completely filled (means all the nodes has 2 children) except the last level which might not be completely full.

Heap Property: All nodes are either greater than equal to (* Max-Heap*) or less than equal to (

*) to each of its child nodes. This is called*

**Min-Heap***.*

**heap property**** How Heap Sort Algorithm works???**

- Sorting in ascending order:
- Create a max Heap from the given input array.
- Extract the root (it will be the maximum value in array) and replace it with the last element in the array.
- Heapify the root of the heap.
- Repeat the steps b and c till entire array is sorted.

- Sorting in descending order
- Create a min Heap from the given input array.
- Extract the root (it will be the minimum value in array) and replace it with the last element in the array.
- Heapify the root of the heap.
- Repeat the steps b and c till entire array is sorted.

**Time Complexity**: O(nLogn)

**See the video below for more understanding**

**Complete Java Code for Heap Sort**:

**Output**:

Original array is: [9, 10, 5, 3, 1, 2, 6] Sorted array is (Heap Sort): [1, 2, 3, 5, 6, 9, 10]