Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case scenarios. The algorithm can be divided into 2 basic parts: [1] Creating a Heap of the unsorted list. [2] Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal. Heap is a tree-based data structure that satisfies two special properties: *** Heap data structure is always a Complete Binary Tree, which means all levels of the tree are fully filled. *** All nodes are either [greater than or equal to] or [less than or equal to] each of its children. If the parent nodes are greater than their children, heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, heap is called Min-Heap.