Heap sort is an improvised form of selection sort, wherein the algorithm initially splits the input vector into sorted and unsorted vectors, and then iteratively shrinks the unsorted vector by extracting the largest element and placing it in the sorted vector. It is based on the heap data structure which provides a non-quadratic asymptote even for the worst-case scenarios. Heaps are tree-based data structures with the following properties:
Shape criterion: Heaps are primarily complete binary trees with both the left and right child nodes filled with values:
Figure 5.10: Illustration of complete and in-complete binary tree
Heap criterion: The ordering of the tree is unidirectional. In other words, all the parent nodes will be greater than the child nodes (max-heap), or all the child nodes will be greater than the parent nodes (min-heap). Either of the heaps can be used for sorting in any required order. In our example, we will use max-heap to sort the input vector in an ascending...