## Introduction

We have come across many different types of sorting algorithms. The use of sorting methods is to ease the rigorous process of sorting one by one, which can be very difficult if performed on a large dataset. Hence, sorting makes our lives easier and builds our thinking skills and the foundations required for later problem-solving.

Heap sort is one of the best techniques possible for sorting, where we first build the __heap __using the given elements. The heap is always a complete binary tree. We use the max heap/ min-heap property to sort the elements in ascending/descending order, respectively. Once the heap has been created satisfying all conditions, we swap the last element with the root element and delete the last node.

Heapify plays a vital role in the heap sort algorithm. We do heapify based on two logics-

i) Building the max heap

ii) Building the min-heap

In the max heap method, we take root as the max element, and then we compare it with its left and right child elements. If the left or right element data is greater than the root element data, we swap the data in both nodes. Then the heapify algorithm is called recursively to the subtree to sort out the subtrees.

Min heap method is similar to the max heap method. We search for a max element in the max heap method. In the min-heap, we will search for the min element.

Heapify is always applied in bottom-up order since heapify can only be performed if its child elements have been heapified.

## Working of Heap Sort using max-heap

Suppose we have an array of [15, 20, 7, 9, 30].

15 |
20 |
7 |
9 |
30 |

0 1 2 3 4

We will be sorting the data in the array in ascending order using the heap sort method. There are two possible ways to sort the array-

- Building Max Heap
- Deleting the data from the max heap

After deleting all the data, we find out that the array is sorted in ascending order.

### 1) Building max heap

When building a tree, the first element to be stored is 15.

After inserting the second element 20, the tree will look like this-

As we know, in a max heap, the parent should be greater than the child element. Therefore we will swap 15 and 20.

Then we will insert seven as the right child element as the heap tree is a complete binary tree(must fill all the levels except the last level).

This satisfies the max heap property, and the level is filled. Hence it will do no swapping here.

Now we will insert 9 in the tree.

Here also, we do not need any swapping and we will be inserting 30 now.

Here we can see that the parent element is less than the child element(15 < 30). Hence we will be swapping both elements.

After checking 30 with its parent element, we see that 20 < 30. Therefore we will swap again.

Now, this is our max heap after sorting, and the array has been sorted like this-

30 |
20 |
7 |
9 |
15 |

0 1 2 3 4

### 2) Deletion of data from the max heap

We have our max heap,

We will delete the first element, and the element to be deleted first in a heap is the root element. After deleting the root element, we will move the last element data into the root node and delete the last element.

15 |
20 |
7 |
9 |
30 |

0 1 2 3 4

After each deletion, we have to check if the tree satisfies the max heap property. As we can see, the left child element of the root is more than the root data(15 < 20), therefore we will be needing swapping here.

20 |
15 |
7 |
9 |
30 |

0 1 2 3 4

Again, we will check if the next child element is satisfying the max heap property or not. We will continue this step till we check with the last element. Now, as the tree is a max heap, the next element to be deleted is 20, and the last element data will be in the root node.

Updating the array-

9 |
15 |
7 |
20 |
30 |

0 1 2 3 4

Now we know it will do swapping as the root element is smaller than the left child element.

15 |
9 |
7 |
20 |
30 |

0 1 2 3 4

The next element to be deleted is the root element 15. The last element to be moved into the top will be the right child element 7.

7 |
9 |
15 |
20 |
30 |

0 1 2 3 4

Since the tree is not satisfying the max heap property, we will swap the elements.

9 |
7 |
15 |
20 |
30 |

0 1 2 3 4

We will be deleting the root element and shifting the last element to the root node.

7 |
9 |
15 |
20 |
30 |

0 1 2 3 4

After deleting the last element 7, the array goes like this-

7 |
9 |
15 |
20 |
30 |

0 1 2 3 4