CREATE OWN LIBRARY

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: