Overview
Heap Sort पहले max-heap बनाता है और हर step में सबसे बड़ा element अंत में रखता है।
Analogy
Priority queue जैसा: हमेशा सबसे बड़ा value पहले निकलता है।
Step-by-step
- array को heapify करके max-heap बनाओ।
- root को last unsorted element से swap करो।
- heap_size को 1 कम करो।
- root से sift-down चलाओ।
- heap_size 1 होने तक repeat करो।
Visual
[heap | sorted tail] में right side का sorted part बढ़ता जाता है।
Common mistakes
- 0-based child index गलत लेना।
- हर extraction के बाद heap_size कम न करना।
- swap के बाद sift-up करना जबकि sift-down चाहिए।
Practice questions
- [4,10,3,5,1] का heapify trace बनाओ।
- बताओ Heap Sort stable क्यों नहीं है।
- descending sort के लिए min-heap variant बनाओ।