Summary

Heap Sort utilizes a Binary Heap (specifically a Max-Heap) to sort elements. A Max-Heap is a complete binary tree where the value of every node is greater than or equal to its children. The algorithm first transforms the array into a Max-Heap. Then, it repeatedly swaps the root (the largest element) with the last element of the heap, reduces the heap size, and "heapifies" the root to restore the Max-Heap property. This process ensures the array is sorted from back to front.

How it Works

• 1. Build Max Heap: Treat the array as a complete binary tree. Start from the last non-leaf node (index n/2 - 1) and iterate backwards to the root (index 0). For each node, perform a heapify operation to ensure the subtree rooted at that node satisfies the Max-Heap property.

• 2. Extract Maximum: The largest element is now at the root (index 0). Swap it with the last element in the current heap range (index i).

• 3. Mark Sorted: The element moved to the end is now in its final sorted position.

• 4. Heapify: Reduce the size of the heap by one. Call heapify on the new root (index 0) to "sift down" the element and restore the Max-Heap property.

• 5. Repeat: Repeat steps 2-4 until the heap size is 1.