Heap Sort

Heap Sort is a comparison-based sorting technique based on a Binary Heap data structure. It is similar to Selection Sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.

Heap Sort is widely known for its excellent efficiency and consistent performance. Since it modifies the array in-place, it does not require additional memory like Merge Sort does.

Complexity

Best Time	Average Time	Worst Time	Space
O(N log N)	O(N log N)	O(N log N)	O(1)

How It Works (Step-by-Step)

1. Build a Max Heap: Rearrange the given array into a Max Heap (a complete binary tree where every parent node is greater than its children).
2. At this point, the largest item is stored at the root of the heap (the first element in the array).
3. Extract the Maximum: Swap the root element with the last element of the heap, effectively moving the largest element to its sorted position at the end of the array.
4. Reduce the heap size by 1 (ignoring the freshly placed sorted element).
5. Heapify: Since the new root might violate the Max Heap property, "heapify" the root down to restore the property.
6. Repeat steps 3-5 until the size of the heap is greater than 1.