Sat Apr 24 2021
Heap sort is a comparison-based sorting algorithm. Heap sort is based on the heap data structure. The asymptotic performance of Heap sort is O(n log n) in the best, average, and worst cases. It is not as fast as Quick sort in the average case, but Heap sort has special properties that will make it particularly useful when sorting data sets too large to fit in main memory.
The basic idea is to turn the array into a binary heap structure, which has the property that it allows efficient retrieval and removal of the maximal element. it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the smallest element and moving that to the sorted region.