Heapsort also works in the similar fashion. In heapsort, ‘Heap’ datastructure is used to maintain the unsorted list and hence the name heapsort. A heap is an array-based data structure visualized as a complete binary tree.
For example let us consider the following array and its corresponding binary tree form
Index 0 1 2 3 4 5 6
Array: 7 6 5 1 3 2 4
1 3 2 4
array contains the root element, and array[2*0+1] contains the left child and array[2*0+2] contains the right child. In general ith node has its left and right children at 2*i+1 and 2*i+2 indices respectively and the parent of ith node will be at array[i/2].
The above heap is also a max-heap in which data at every node is greater than those of its children.
In this algorithm, all the elements are formed into a max-heap by repeatedly using heapify procedure. heapify procedure works on any node which violates the max-heap property. for example let us consider the following heap is not a max-heap because 2 is less than it’s children.
to correct this we will swap 2 and 6 ( bigger child) and recursively apply the same procedure for the node 2.
violation <—- 2 5
So the following heap is a max-heap now.
The build heap procedure scans through all the non-leaf nodes and calls the heapify procedure.
Finally the heap contains the maximum element at the root of the heap ( array ). To sort the array. We swap the root element with the end element (array[length-1]). Now the heap may violate the max heap property at the root node. so call the heapify procedure. Next time we can exclude the last element because it is it’s correct place. The heap size is reduced by one.
The following Java Program implements the above algorithm.