Heap sort — O(n log n), in-place, not stable
WHAT is a heap?
HOW the algorithm runs
Two phases:
- Build-max-heap: turn the raw array into a heap.
- Sort-down: times, swap root with last element, shrink heap, re-heapify root.
The workhorse is sift-down (a.k.a. heapify): given a node whose subtrees are already heaps but whose own value may be too small, push it down to its correct level.
sift_down(A, i, n): # heap occupies A[0..n-1]
while True:
l, r = 2i+1, 2i+2
largest = i
if l < n and A[l] > A[largest]: largest = l
if r < n and A[r] > A[largest]: largest = r
if largest == i: break
swap(A[i], A[largest])
i = largest
heap_sort(A):
n = len(A)
for i = n//2 - 1 down to 0: # build heap
sift_down(A, i, n)
for end = n-1 down to 1: # sort
swap(A[0], A[end]) # crown to the back
sift_down(A, 0, end) # re-heapify shrunken heap
![[3.6.05-Heap-sort-—-O(n-log
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Heap sort ko samajhne ka sabse easy tareeka: ek max-heap banao, jo ek "complete binary tree" hota hai array ke andar stored — yaani har parent apne dono children se bada hota hai, aur root hamesha sabse bada (max) hota hai. Pointers ki zaroorat nahi, kyunki index formula se chal jaata hai: parent = (i-1)//2, left = 2i+1, right = 2i+2. Yeh array trick hi heap sort ko in-place banata hai — koi extra memory nahi chahiye.
Algorithm do phase mein chalta hai. Pehle build-heap: index n/2-1 se 0 tak sift_down karo (leaves skip, kyunki single node already heap hai). Yeh phase surprisingly sirf O(n) hai — proof: , kyunki zyada nodes leaves ke paas hote hain jo bahut kam sift karte hain. Phir sort-down: root (max) ko array ke last position pe swap karo, heap ka size ek se chhota karo, aur root pe dobara sift_down chalao. Yeh baar karo, har baar ek ki cost — total O(n log n), har case mein (best/avg/worst sab same).
Ascending order chahiye to max-heap use karo, min-heap nahi — kyunki nikala hua max peeche jaata hai, to bade element back mein settle hote hain. Important baat: heap sort stable nahi hai. Equal keys ka original order toot jaata hai, kyunki swaps lambi duri pe jump karte hain aur kisi ko yaad nahi rehta ki pehle kaun aaya tha. Isliye agar stability chahiye to merge sort use karo; agar guaranteed O(n log n) aur in-place chahiye bina worst-case risk ke (quicksort ke ulat), to heap sort best hai.