Heapify — bottom-up O(n) build — Hinglish notes

3.4.11 · Coding › Trees

WHAT is heapify?

Array ↔ tree index map (0-based):

$i$ ka parent: $⌊(i - 1) /2 ⌋$
$i$ ka left child: $2 i + 1$
$i$ ka right child: $2 i + 2$
Last internal (non-leaf) node: index $⌊ n /2 ⌋ - 1$ (iske baad sab leaf hain).

HOW: the `siftDown` operation

siftDown(i) yeh assume karta hai ki i ke children ki roots wali subtrees already valid heaps hain, aur A[i] ko tab tak neeche push karta hai jab tak heap property hold na kare.

siftDown(A, i, n):
    while True:
        l = 2*i + 1
        r = 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          # parent already biggest
        swap(A[i], A[largest])
        i = largest                     # follow the swap down

buildHeap(A, n):
    for i from floor(n/2)-1 down to 0:
        siftDown(A, i, n)

DERIVATION: yeh $O (n)$ kyun hai, $O (n lo g n)$ kyun nahi?

Setup. $n$ nodes wale complete binary tree ki height $h = ⌊ lo g_{2} n ⌋$ hoti hai. Node height ko bottom se measure karo: leaves ki height $0$ hoti hai, root ki height $h$ .

Ek siftDown ki cost. Height $k$ wala node zyada se zyada $k$ levels neechie sink ho sakta hai, toh uska kaam $O (k)$ hai.

Har height pe nodes count karo. Ek (lagbhag-)complete tree mein height $k$ pe zyada se zyada $⌈ n / 2^{k + 1} ⌉$ nodes hote hain.

Total kaam ka sum karo.

T (n) = k = 0 \sum h count \frac{n}{2 ^{k + 1}} \cdot cost O (k) = O (n k = 0 \sum h \frac{k}{2 ^{k + 1}}) \leq O (\frac{n}{2} k = 0 \sum \infty \frac{k}{2 ^{k}}) .

Ab ek key infinite sum evaluate karo. Standard identity use karo (neeche derive ki gayi hai):

k = 0 \sum \infty k x^{k} = \frac{x}{( 1 - x ) ^{2}}, ∣ x ∣ < 1.

$x = \frac{1}{2}$ plug karo:

k = 0 \sum \infty \frac{k}{2 ^{k}} = \frac{1/2}{( 1 - 1/2 ) ^{2}} = \frac{1/2}{1/4} = 2.

Isliye

T (n) \leq O (\frac{n}{2} \cdot 2) = O (n) .

Worked examples

Worked example Example 1 —

[3, 9, 2, 1, 4, 5] se max-heap banao $n = 6$ , last internal node $= ⌊ 6/2 ⌋ - 1 = 2$ . $i = 2, 1, 0$ process karo.

Tree (indices): 0=3, 1=9, 2=2, 3=1, 4=4, 5=5.

i=2 (value 2, children idx 5=5): 5>2 → swap. Array: [3,9,5,1,4,2]. Yeh step kyun? Node 2 ka ek hi child (5) bada hai, toh parent ko woh value leni chahiye.

i=1 (value 9, children idx 3=1, 4=4): dono chhote hain → koi swap nahi. [3,9,5,1,4,2]. Yeh step kyun? 9 already dono children se $\geq$ hai — heap property locally hold karti hai.

i=0 (value 3, children idx 1=9, 2=5): largest 9 hai → idx 1 se swap. [9,3,5,1,4,2]. Ab idx 1 pe 3 ko sift karo: children idx 3=1, 4=4 → 4 largest hai → swap. [9,4,5,1,3,2]. Node ab idx 4 pe leaf hai → ruk jao. Yeh step kyun? Root pe swap karne ke baad, demoted value (3) neeche bhi property violate kar sakti hai, toh hum usse follow karte rahe neeche tak.

Result: [9,4,5,1,3,2] — valid max-heap (check: 9≥4,5; 4≥1,3; 5≥2 ✓).

Common mistakes

Recall Feynman: ek 12-saal ke bacche ko samjhao

Ek tournament bracket socho jo ek pyramid ki tarah drawn hai jisme log hain, sabse bada aur taqatwar upar hona chahiye. Zyaatar log bottom rows mein khade hain — bahut saare hain, lekin har ek ko sirf ek ya do log se larna padta hai jo seedha unke upar hain: sasta. Upar jaate jaate, bahut kam log hote hain, aur sirf unhe hi lambi charhaayi karni padti hai. Kyunki bheedbhad wala bottom sasta hai aur lambi charhaiyan rare hain, total kushti sirf "har insaan ke liye lagbhag ek match" hoti hai — yeh log ki sankhya ke saath seedhi line mein badhti hai, zyada tezi se nahi.

Flashcards

Bottom-up heapify ki time complexity kya hai?

O (n)

(linear), loose

O (n lo g n)

bound se tighter.

Bottom-up build-heap kis index se start karta hai?

Last internal node,

⌊ n /2 ⌋ - 1

(iske baad sab leaf hain).

Build-heap mein nodes ko bottom se top kyun process karte hain?

siftDown(i) ke liye zaroori hai ki dono children ki subtrees already valid heaps hon; bottom-up yeh ordering guarantee karta hai.

Height

k

wale node pe siftDown ki cost?

O (k)

— woh zyada se zyada

k

levels sink ho sakta hai.

Height

k

pe kitne nodes hote hain (zyada se zyada)?

Lagbhag

n / 2^{k + 1}

; unche nodes exponentially rare hain.

Kaun sa infinite sum

O (n)

bound prove karta hai, aur uski value?

\sum_{k = 0}^{\infty} k / 2^{k} = 2

, ek constant.

\sum k x^{k}

derive karo.

\sum x^{k} = 1/ (1 - x)

ko differentiate karo taaki

\sum k x^{k - 1} = 1/ (1 - x)^{2}

mile, phir

x

se multiply karo:

\sum k x^{k} = x / (1 - x)^{2}

Insertion-based build

O (n lo g n)

kyun hai lekin siftDown build

O (n)

kyun?

siftUp numerous leaves ko root ki taraf move karta hai (mehenga direction); siftDown lambi path sirf rare unche nodes ko deta hai.

Children/parent index formulas (0-based)?

left

= 2 i + 1

, right

= 2 i + 2

, parent

= ⌊(i - 1) /2 ⌋

Leaves kyun skip kiye jaate hain?

Ek single node already valid heap hai; use sift karna wasted work hai aur out-of-bounds child access ka risk hai.

Connections

Binary Heap — woh data structure jo heapify produce karta hai.
Heapsort — build-heap ( $O (n)$ ) use karta hai phir $n$ extract-max ( $O (n lo g n)$ ).
Priority Queue — heaps iska standard implementation hain.
Complete Binary Tree — array↔tree index mapping.
Geometric Series / Amortized Analysis — linear bound ke peeche ka summation trick.
siftUp vs siftDown — direction complexity kyun decide karta hai.