3.4.10
Intuition Ek line mein pictureEk heap ek complete binary tree hota hai jahan har parent apne children se "zyada extreme" hota hai. Max-heap mein har parent ≥ uske children (sabse bada root pe); min-heap mein har parent ≤ uske children (sabse chota root pe). Bus itna hi hai — poora data structure ek local rule hai jo har jagah apply hota hai.
Intuition DO alag properties KYU?
Shape property tree ko balanced rakhti hai → height hamesha ⌊ log 2 n ⌋ Order property extreme element ko top pe rakhti hai → peek O ( 1 ) bhi hai aur upar se sorted bhi — exactly wahi jo ek priority queue ko chahiye.
Common mistake Steel-man: "Heap sorted hoti hai, jaise BST."Kyun sahi lagta hai: root max/min hai aur parents children pe dominant hain — ordered lagta hai.
Kyun galat hai: heap sirf ek path ke along order karta hai (ancestor vs descendant). Siblings unordered hote hain. Ek max-heap mein, [9, 5, 8, 1, 4] valid hai chahe left child 5 right subtree ke 8 se chota ho. Isliye aap BST ki tarah O ( log n ) nahi kar sakte. Heap sirf ek sawaal ka fast jawab deta hai: "extreme element kaunsa hai?"
Intuition Pointer nahin, array KYU?Kyunki tree complete hai, koi "gaps" nahi hote. Isliye hum nodes ko level by level ek contiguous array mein rakh sakte hain aur child/parent positions ko arithmetic se compute kar sakte hain — koi node objects nahi, koi pointers nahi, cache-friendly.
Common mistake Steel-man: 1-based vs 0-based index confusionKyun sahi lagta hai: bahut saari textbooks (CLRS) 1-based use karti hain jahan left = 2 i right = 2 i + 1 parent = ⌊ i /2 ⌋ Fix: ek choose karo. Code mein (0-based arrays) hamesha 2 i + 1 , 2 i + 2 , ⌊( i − 1 ) /2 ⌋
Worked example 1. Kya yeh array ek valid max-heap hai?[9, 5, 8, 1, 4, 7]
Har parent check karo (indices 0 , 1 , 2 3 , 4 , 5
i = 0 9 ≥ 5 9 ≥ 8 Yeh step kyun? root ko dono children pe dominate karna chahiye.i = 1 5 ≥ 1 5 ≥ 4 i = 2 8 ≥ 7 Verdict: valid max-heap. Note karo 5 < 8 (siblings unordered hain) — bilkul theek hai.
Worked example 2. Sift-down (max-heapify) se ek violation fix karo. Start[3, 9, 8, 5, 4]
Root 3 violate kar raha hai (3 < 9 Sift-down kyun? bad element apni position ke liye bahut chota hai, isliye ise leaves ki taraf push karo.
i = 0 3 < 9 [9,3,8,5,4]. Bade se swap kyun? chhote se swap karne par woh bada child apne sibling se upar reh jaata? Nahi — hum bade se swap karte hain taaki naya parent (9) doosre child (8) se bhi ≥ rahe, automatically.Index i = 1 3 < 5 [9,5,8,3,4].
i = 3 Result [9,5,8,3,4] ek valid max-heap hai. Path walked = height = O ( log n )
Worked example 3. Min-heap[2, 4, 3, 7, 9] mein 10 insert karo phir sift-up karo
Pehle append kyun? Sirf wahi jagah jahan shape complete rehti hai woh next free leaf hai.
Append: [2,4,3,7,9,10], naya element index 5.
parent ( 5 ) = ⌊ 4/2 ⌋ = 2 3 ≤ 10
Ab 1 insert karo: [2,4,3,7,9,1], index 5.
parent(5)=2 (val 3). 3 ≤ 1 [2,4,1,7,9,3].
ab index 2 pe, parent(2)=⌊ 1/2 ⌋ = 0 2 ≤ 1 [1,4,2,7,9,3].
index 0 root hai → stop. Valid min-heap, 1 top pe bubble ho gaya.
Recall Active recall (answers cover karo)
Heap ko define karne wali do properties kya hain? → shape (complete tree) + heap-order (parent vs child) .
Max-heap root kya hota hai? → maximum . Min-heap root? → minimum .
Kya siblings ordered hote hain? → Nahi.
0-based: i 2 i + 1 , 2 i + 2 ⌊( i − 1 ) /2 ⌋
n ⌊ log 2 n ⌋ Heap mein BST ki tarah O ( log n )
Recall Feynman: 12-saal ke bachche ko explain karoSocho ek pyramid of people jahan har boss unke directly neeche wale logon se lamba hai. Sabse lamba banda hamesha bilkul upar hota hai — usse tum turant dekh sakte ho. Lekin do side-by-side log kisi bhi height ke ho sakte hain; hum unhe kabhi compare nahi karte. Jab koi naya banda join karta hai, woh neeche ki next khaali jagah pe khada hota hai, phir apne boss ke saath upar ki taraf swap karta rehta hai jab tak usse upar koi lamba nahi milta. Yeh swapping choti hoti hai kyunki pyramid wide hoti hai aur bahut lambi nahi — isliye hamesha jaldi ho jaata hai.
Mnemonic Rules yaad karne ka tarika"Mom is the eXtreme" → maX -heap, parents bade hote hain. Aur "Children Lie at 2i+1, 2i+2" . Min-heap ke liye: "sabse chota surface pe swim karta hai."
Priority Queue — heaps ka main use (insert + extract-min/max).Heapsort — build-heap phir baar baar root extract karo.Complete Binary Tree — shape property ki foundation.Binary Search Tree — contrast: BST siblings order karta hai, heap nahi karta.Build-Heap (Heapify) O(n) — bottom-up sift-down.Big-O Notation — kyun har operation O ( log n )
Har heap ko kaunsi do properties satisfy karni chahiye? Shape (complete binary tree, last level left-to-right fill) aur heap-order (parent vs child relation).
Max-heap mein maximum element kahan hota hai? Root pe (index 0).
Min-heap mein minimum element kahan hota hai? Root pe (index 0).
Kya heap mein sibling nodes ordered hote hain? Nahi — sirf ancestor–descendant pairs ordered hote hain; siblings kisi bhi order mein ho sakte hain.
0-based: node i ke left aur right children ke indices? 2i+1 aur 2i+2.
0-based: node i ke parent ka index? floor((i-1)/2).
n nodes wale heap ki height kya hoti hai? floor(log2(n)).
Heap mein insert/extract O(log n) kyun hai? Sift-up/sift-down zyada se zyada ek root-to-leaf path walk karta hai jis ki length = height = O(log n) hai.
Heap ko BST ki tarah O(log n) mein search kyun nahi kiya ja sakta? Siblings unordered hote hain, isliye comparison se tree ka aadha hissa discard nahi kiya ja sakta.
Insert karte waqt naya element pehle kahan jaata hai aur kyun? Next free leaf pe (last array slot) taaki complete-tree shape preserve ho, phir sift up hota hai.
Max-heapify (sift-down) mein bade ya chhote child se swap karte hain, aur kyun? Bade child se, taaki naya parent doosre child pe bhi dominate kare, max-heap property maintain rahe.
left 2i+1 right 2i+2 parent floor i-1 over 2
Not a BST no O log n search
