What is Heap Sort?

Heap Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting and a family member of the selection sort. As the name suggests, this sorting algorithm use the concept of a heap structure that is based on the binary tree, which works as follows:
1. Using an array and the given data items, build a heap i.e. either a min heap or max heap as per requested sorting order
2. From the heap, remove the root node's data items and insert it to an separate array
3. Wait until the heap orders is restored, which will produces a new root node. Now, recursively repeat the above procedure '2' until there is no data items left in the heap.

Click the link -> Heap Sort for the pseudocode