Heap Sort uses a data structure called a max-heap — a binary tree where every parent is larger than its children. Once you build this heap, the largest element is always sitting at the root. Extract it, shrink the heap, fix the heap property, and repeat until sorted.
It's in-place (O(1) extra space), always O(n log n) regardless of input, and uses the heap data structure in a way that makes both the structure and the sort click at the same time.
Every parent node is larger than both its children. The root is always the maximum element. This is enforced by the heapify operation.
Phase 1: build the max-heap (O(n)). Phase 2: extract the root n times, each time calling heapify to restore the heap (O(n log n) total).
Unlike Quick Sort, Heap Sort has no bad inputs. Sorted, reverse-sorted, random — always O(n log n). This makes it reliable for critical systems.
Heap Sort sorts the array in-place using O(1) extra space. The heap is built within the input array itself, not a separate structure.
TIPWatch the tree carefully during heapify. When a parent swaps with a child, the recursion follows the swapped node down — because the swap might have violated the heap property further down the tree.
COLOUR LEGEND
In heap — being heapified Being swapped / extracted Sorted — in final position