Overview
Heap Sort pehle max-heap banata hai, phir har round me biggest element ko end me place karta hai.
Analogy
Priority queue jaisa behavior: sabse bada value pehle nikalta hai.
Step-by-step
- array ka heapify karke max-heap banao.
- root ko last unsorted element ke saath swap karo.
- heap_size ek kam karo.
- root se sift-down chalao.
- heap_size 1 tak repeat karo.
Visual
[heap | sorted tail] me right side ka sorted part grow hota hai.
Common mistakes
- 0-based indexing me child index formula galat lagana.
- extraction ke baad heap_size update na karna.
- swap ke baad sift-up use karna instead of sift-down.
Practice questions
- [4,10,3,5,1] ka heapify step trace karo.
- Explain karo Heap Sort stable kyu nahi hai.
- min-heap use karke descending sort banao.