Heap Sort

Explanation

- **Heap Sort** is a comparison-based sorting algorithm that uses a binary heap data structure. The algorithm works by building a max heap (or min heap) and then repeatedly extracting the largest (or smallest) element and rebuilding the heap until the list is sorted.
-

• Steps:

  • Build a max heap from the input data.
  • Swap the root of the heap (the maximum element) with the last element in the heap.
  • Reduce the size of the heap by 1 and heapify the root of the tree.
  • Repeat the process until the heap is empty.

• Time Complexity:

  • Best Case, Average Case, Worst Case: O(n log n)