Heap sort — in-place, O(n log n) — Hinglish notes

3.4.13 · Coding › Trees

Heap (array mein) KYA hota hai?

Array kyun, pointers kyun nahi? Ek complete tree mein koi hole nahi hota — har level full hoti hai sivaaye possibly last level ke, jo left-to-right bhari jaati hai. Woh regular shape matlab hum child/parent positions arithmetic se calculate kar sakte hain, toh hume zero pointers aur zero extra memory chahiye. Yahi hai "in-place" ka raaz.

Recall Kyun

parent = (i-1)/2 hai? $p$ ka left child $2 p + 1$ hai, right $2 p + 2$ hai. Dono ko invert karo: $2 p + 1$ se $p = (i - 1) /2$ milta hai; $2 p + 2$ se $p = (i - 2) /2$ milta hai. $(i - 1) /2$ ka integer floor division dono cases ko ek formula mein combine kar deta hai.

Algorithm KA KAAM (do phases)

Phase 1 — Heap banana (poore array ko heapify karna)

Ek unordered array ko max-heap mein badalna.

Phase 2 — Repeated extraction se sorting

Root (max) ko last heap slot se swap karo, heap ko ek se chhota karo, naye root ko neeche sift karo. Repeat karo.

Dono ke liye main engine hai sift-down (a.k.a. max_heapify).

Figure — Heap sort — in-place, O(n log n)

def sift_down(A, i, n):          # heap occupies A[0..n-1]
    while True:
        l, r = 2*i + 1, 2*i + 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        # heap property restored
        A[i], A[largest] = A[largest], A[i]
        i = largest                   # follow the swap downward
 
def heap_sort(A):
    n = len(A)
    # Phase 1: build max-heap, bottom-up from last parent
    for i in range(n//2 - 1, -1, -1):
        sift_down(A, i, n)
    # Phase 2: extract max repeatedly
    for end in range(n - 1, 0, -1):
        A[0], A[end] = A[end], A[0]   # biggest -> sorted tail
        sift_down(A, 0, end)          # restore heap of size `end`

Time complexity ka derivation

Phase 2 $O (n lo g n)$ hai — aasaan

Hum $n - 1$ extractions karte hain, har ek $\leq n$ size ke heap par sift-down hai: $\sum_{k = 1}^{n - 1} O (lo g k) = O (n lo g n) .$

Phase 1 (build) $O (n)$ hai — surprising!

Naive guess: $n$ nodes $\times lo g n$ = $O (n lo g n)$ . Tight truth: zyaatar nodes bottom ke paas hote hain aur sift-down thoda hi karta hai.

Bottom se height $h$ par zyada se zyada $⌈ n / 2^{h + 1} ⌉$ nodes hote hain, har ek ka cost $O (h)$ : $T_{build} = \sum_{h = 0}^{⌊ l o g n ⌋} \frac{n}{2 ^{h + 1}} O (h) = O (n \sum_{h = 0}^{\infty} \frac{h}{2 ^{h}}) .$ Ab series evaluate karo. Maano $S = \sum_{h \geq 0} h x^{h} = \frac{x}{( 1 - x ) ^{2}}$ . $x = \frac{1}{2}$ par: $S = \frac{1/2}{( 1/2 ) ^{2}} = 2$ . Isliye $T_{build} = O (2 n) = O (n) .$

Worked examples

Common mistakes (steel-manned)

Flashcards

Heap sort time complexity (best, average, worst)

O (n lo g n)

teeno cases mein.

Heap sort extra space

O (1)

— fully in-place (iterative sift-down).

Kya heap sort stable hai?

Nahi — sifting swaps equal keys ka order bigaad dete hain.

Node

i

(0-based) ke left child ka index

2 i + 1

Node

i

(0-based) ke parent ka index

⌊(i - 1) /2 ⌋

Build-heap loop kahaan se shuru hoti hai?

Last internal node se, index

⌊ n /2 ⌋ - 1

, neeche 0 tak.

Build-heap

O (n)

kyun hai,

O (n lo g n)

kyun nahi?

Zyaatar nodes bottom ke paas hain;

\sum_{h} (n / 2^{h + 1}) \cdot h = O (n)

kyunki

\sum h / 2^{h} = 2

Sift-down ka precondition kya hai?

Node

i

ke dono subtrees already valid heaps hain.

Phase 2 step ek line mein

Root ko last heap slot se swap karo, heap chhota karo, naye root ko sift-down karo.

Ascending sort ke liye max-heap vs min-heap?

Max-heap use karo; har round mein sabse bada end mein park hota hai.

Heap array mein store — pointers kyun nahi?

Yeh complete tree hai, toh child/parent positions pure index arithmetic se milti hain.

Recall Feynman: ek 12-saal ke bacche ko samjhao

Socho numbered cards ka ek pyramid hai, jisme rule hai ki har card apne neeche wale dono cards se bada hota hai. Toh sabse bada card hamesha upar hota hai. Unhe sort karne ke liye: sabse upar wala (sabse bada) card uthao aur apni row ke bilkul end mein rakh do. Ab ek chota card upar aa gaya aur rule toot gaya, toh use "sink" hone do — use neeche wale dono cards mein se bade wale se swap karte raho jab tak pyramid ka rule phir fix na ho jaaye. Ab naya top next-biggest hai; use last wale se thoda pehle park karo. Repeat karo jab tak pyramid khaali na ho — teri row sort ho gayi, aur tujhe iske liye koi doosri table nahi chahiye thi!

Connections

Binary Heap — woh data structure jis par heap sort run karta hai.
Priority Queue — same heap, repeated min/max access ke liye use hota hai.
Quicksort — yeh bhi in-place hai lekin worst case $O (n^{2})$ hai; heap sort $O (n lo g n)$ guarantee karta hai.
Merge Sort — $O (n lo g n)$ aur stable hai, lekin $O (n)$ extra space chahiye.
Complete Binary Tree — isliye index arithmetic kaam karta hai.
Big-O Notation — build-heap series analysis ke liye.
Introsort — hybrid jo quicksort ke worst case se bachne ke liye heap sort par fall back karta hai.