Overview
Heap Sort builds a max-heap, then repeatedly extracts the max to the end of the array.
Analogy
Priority queue of tasks: always pop the top priority and place it at the back of the timeline.
Step-by-step
- Heapify the array into a max-heap (bottom-up).
- For end from n-1 down to 1:
- Swap arr[0] (max) with arr[end].
- Reduce heap size by 1.
- Sift-down arr[0] to restore heap property.
Visual
Binary tree where parent ≥ children; max bubbles to root then moves to sorted tail.
Common mistakes
- Mixing 0-based and 1-based child index formulas.
- Forgetting to shrink heap size after each extraction.
- Heapifying top-down (O(n log n)) instead of bottom-up (O(n)).
Practice questions
- Heapify [4,10,3,5,1] step by step.
- Explain why heap sort is not stable.
- Use min-heap to sort descending.
AI Wisdom