Heap operations — insert O(log n), extract-max - min O(log n), decrease-key

3.4.12 · Coding › Trees

Dono repair primitives (sab kuch inhi se banta hai)

decrease-key (min-heap) / increase-key (max-heap) — $O (lo g n)$

Common mistake Steel-manned errors

❌ "extract-max ko root ko last leaf ke saath nahi, balki largest child ke saath swap karna chahiye." Kyun sahi lagta hai: largest child naturally successor lagta hai. Fix: agar tum ek child ko promote karo toh beech mein ek hole ban jaata hai → tree ab complete nahi rehti → array indexing toot jaati hai. Hamesha pehle last element upar laao, phir sift-down karo.

❌ "min-heap par decrease-key ko sift-down chahiye." Kyun sahi lagta hai: "decrease" ka matlab "neeche jaana" lagta hai. Fix: ek choti value upar belong karti hai (min-heap mein root ke kareeb), toh usse chadhna chahiye — sift-up use karo.

❌ "0-indexed arrays mein parent(i) = i/2 hota hai." 1-indexed textbooks se sahi lagta hai. Fix: 0-indexed parent $⌊(i - 1) /2 ⌋$ hai. Check karo $i = 2$ : $i /2 = 1$ galat hai, $(i - 1) /2 = 0$ ✓.

❌ "Heaps sorted hote hain." Isliye sahi lagta hai kyunki max front par hai. Fix: siblings ke beech koi order nahi hota; sirf parent–child chain ordered hai.

Cost summary (Forecast-then-Verify)

Operation	Steps	Time
peek max/min	$A [0]$ padho	$O (1)$
insert	append + sift-up	$O (lo g n)$
extract-max/min	last→root swap, sift-down	$O (lo g n)$
decrease/increase-key	update + sift-up	$O (lo g n)$
build-heap (bonus)	$n /2 - 1$ se 0 tak sift-down	$O (n)$

Max-heap ki heap property kya hai?

Har parent ≥ dono children (root maximum hai).

0-indexed: node i ke children?

left = 2i+1, right = 2i+2.

0-indexed: node i ka parent?

floor((i-1)/2).

Heap mein insert algorithm?

Nayi key index n par append karo (tree complete rehti hai), phir property restore karne ke liye sift-up karo. O(log n).

Insert O(log n) kyun hai O(n) nahi?

sift-up ek hi path par swap karta hai jiska length ≤ height = floor(log2 n) hai.

extract-max ke steps?

A[0] save karo; last element ko root mein laao; size ghataao; sift-down(0) karo; saved max return karo.

extract mein LAST element ko root mein kyun laate hain?

Yeh O(1) mein completeness preserve karta hai; koi child promote karne se beech mein hole ban jaata aur array indexing toot jaati.

Min-heap par decrease-key kaun sa primitive use karta hai?

sift-up — choti value upar belonging karti hai.

Max-heap par increase-key kaun sa primitive use karta hai?

sift-up — badi value upar belonging karti hai.

Peek O(1) kyun hai lekin extract O(log n) kyun?

Peek sirf A[0] padhta hai; extract ko ek root-to-leaf path rebalance karna padta hai.

Heap mein siblings ordered hote hain?

Nahi — sirf parent–child chain ordered hai; heaps fully sorted nahi hote.

Ek array se heap banana ka time?

O(n) via index n/2-1 se 0 tak sift-down karo.

Recall Feynman: 12 saal ke bacche ko samjhao

Socho logon ka ek pyramid jahan har boss apne neeche wale dono logon ke upar khada hai aur unse lamba hai. Sabse lamba insaan hamesha upar hota hai, toh sabse lamba dhundhna ekdum instant hai. Jab koi naya insaan aata hai, woh neeche khali jagah par khada hota hai aur apne boss ke saath tab tak swap karta rehta hai jab tak woh lamba ho — woh utna hi upar jaata hai jitna deserve karta hai. Jab top wala insaan chala jaata hai, hum bilkul last wale insaan ko upar laate hain (taaki koi gap na ho), phir use apne sabse lambe bacche ke saath position swap karte karte neeche utarne dete hain jab tak upar wale sab lambe na ho jayein. Har chadhna ya utarna sirf pyramid mein ek seedhi line hai, aur pyramid chota hai (lagbhag $lo g n$ floors), toh yeh fast hai.

Heap operations — insert O(log n), extract-max - min O(log n), decrease-key

Heap KYA hai (definition)

Dono repair primitives (sab kuch inhi se banta hai)

sift-up (bubble-up)

sift-down (heapify-down)

insert — $O (lo g n)$

extract-max — $O (lo g n)$

decrease-key (min-heap) / increase-key (max-heap) — $O (lo g n)$

Cost summary (Forecast-then-Verify)

Concept Map