**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 of Heapsort:**

**1. **Build the given tree as **Max-heap** where every root element should larger compare two its Childs.

**2.** Remove the root element and place it to end of the array i.e. end of the tree as a vacant place.

**3.** Now, run **Max heapify** to rebuild the new tree as a Max heap.

**4.** Same way process will be continued until the end of the tree and all elements are sorted.

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

The **array is sorted** now:

** INPUT:** An unsorted array a[6,2,4,1,…………….,n]

** OUTPUT:** An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)

PROCESS:

**Step 1: [read the number of elements and array elements]**

Read n

For i = 0 to n repeat

Read arr[i]

**Step 2: [‘MAX_HEAPIFY’ function to arrange the elements of the array]**

MAX_HEAPIFY(A, i)

{ l = 2i

r = 2i + 1

if(l <= A.heap_size and A[l] > A[i])

largest = l;

else

largest = i;

if(r <= A.heap_size and A[r] > A[largest])

largest = r;

If( largest i)

exchange A[i] with A[largest]

MAX_HEAPIFY(A, largest)

}

**Step 3: [‘**HeapSort**’ function to sort the array]**

HeapSort(A)

{ Build_MAX_Heap(A)

for(i = A.length down to i)

exchange A[1] with A[i]

A.heap_size = A.heap_size – 1

MAX_HEAPIFY(A, 1)

}

**Step 4: [display the sorted array]**

For i =0 to n repeat

Print A[i]

[End of ‘for’ loop]

__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.

HeapSort(A)

{ **Build_MAX_Heap(A)** --------------- **O(n)**

**for(i = A.length down to i)** ----------- **n-1**

exchange A[1] with A[i]

A.heap_size = A.heap_size – 1

**MAX_HEAPIFY(A, 1)** -------------------- **n-1 * O(logn)**

}

**Therefore the time complexity of heap sort is:**

The complexity is the same for all three cases i.e. **Best case**, the **average case,** and the **worst case**.

__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

- Merge Sort Iterative
- Merge Sort using recursion
- Quick Sort using recursion
- Quicksort Iterative
- Insertion Sort
- Selection Sort
- Bubble Sort
- 3 way Merge Sort
- Heap Sort Iterative
- 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