**Heapsort** is a **comparison based sorting technique** which is depending on the data structure of the **binary heap**. **A complete binary tree in** **the** **data structure is a binary tree** in which every level is completely filled except the last level. The heap binary tree can be of two types- **max heap** and **min-heap**. When the parent node is greater than the left and right child then the tree is known as max heap and when the parent node is lesser than the left and right child then the tree is known as **min-heap**. It is an **in-place **sorting algorithm as it does not require any extra storage space to sort the data. **The ****heapsort**** algorithm is divided into two parts**. In the first part, the heap tree is built and in the second step the array is sorted by removing the largest element from the array repeatedly and inserting it at its sorted position and after that, the heap tree is created again. In the array representation of heap tree, if the parent node is at index i then its **left child** will be at **index 2*i**, and the **right child** will be at **index 2*i + 1**.

**Procedure with an example:**

Suppose there is an array of **5 elements** as following:

The array has to be sorted in ascending order and we are following the **max heap tree** to **sort the elements**. We are considering the array to be started from index 0. So the **left child** will be at the **index 2*i + 1** and the **right child** will be at the **index 2*i + 2**.

First, the **heap tree** will be **created following the ****max heap**** data structure**. So **3** will be **compared** to **2**** and ****4 **(the two children of 3) and as **4**** is greater than ****3**, they will **be ****swapped**. Now the array will be:

Again **-9** will be **compared to ****4**** and ****12**, in this case **both are greater than ****-9** but as **12**** is greater in between two children** then **-9** will be **swapped**** with**** 12** and the array will be:

Now, the **max heap**** is built**.

The **2nd part** is now to eliminate the root (largest element of the array) and will be put at the last node of the tree (last index in array) and also insert the last element as the root.

**Step 1:**

Now we are **not**** considering ****12** (removed element) in the tree.

Now, again the **max heap** will be built from **index ****0 ****to ****n-1** in a previous way. **First ****4** is **compared** with its **left child 2**, as **2 is lesser than 4** so there will be no change. Now **3, the root **node will be compared with its **left and right child 4 and -9 respectively**, as **4 is greater than the root node 3** then **it will be swapped.**

Now again the **maximum element will be eliminated** again as the following:

**Step 2:**

Now we are **not**** considering ****element 4** (removed element) in the tree.

Again the **max heap** will be built using **max heapify**** procedure**:

Now again the **root** (**maximum element) will be eliminated** again like the following:

**Step 3:**

Now the same way we are **not**** considering ****element 3** (removed element) in the tree.

Again the **max heap** will be built using **max heapify**** procedure**:

Now again the **root** (**maximum element) will be eliminated** again like the following:

**Step 4:**

__CHARACTERISTICS:__

**1. **It is a **comparison based** sorting technique.

**2. **It is an **in-place** sorting mechanism that does not require any extra storage space for sorting.

**3. **It can be thought of as an improved **selection sort**.

**4. **The **heap tree** can be represented using an array.

__TIME COMPLEXITY:__

The time taken to **build the heap** for n elements is **O(n)**.

Each of the **n -1 calls **to arrange the element using the **MAX_HEAPIFY** function takes **O(logn)** time.

The time complexity of **recursive** and **iterative heapsort** is the same: **O(nlogn)**

**For more details please follow the** **time complexity of recursion heapsort: **

__https://mycareerwise.com/programming/category/sorting/heap-sort-using-recursion__

__SPACE COMPLEXITY:__

The space complexity is ** ****O(1)** as no extra space is needed to sort the elements of the array.

__ADVANTAGES:__

**1. **It is an efficient sorting algorithm.

**2. **It is a simple algorithm that can be implemented very easily.

**3. **It performs equally for best case, average case and worst case i.e. Its performance is consistent.

**4. **It does not require any extra storage space to sort the elements.

__DISADVANTAGES:__

**1. **It is an unstable sorting algorithm.

**2. **Storing the data in heap is slower than storing data in a stack.

__APPLICATION:__

**1. **It is used in interval scheduling.

**2. **Heapsort is applied in the priority queue.

Related

- Heap Sort using recursion
- Merge Sort Iterative
- Merge Sort using recursion
- Quick Sort using recursion
- Quicksort Iterative
- Insertion Sort
- Selection Sort
- Bubble Sort
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort

Contributed by