Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm): Visual walkthrough

3.7.4 · D2 · Coding › Algorithm Paradigms › Greedy problems — activity selection, fractional knapsack, H

Hum sirf parent topic ke Huffman section ko touch karte hain, aur teen helpers ka sahara lete hain jab woh aate hain: Priority Queue / Binary Heap (woh machine jo humein sabse chhota item deti hai), Exchange Argument (proof ka style), aur Prefix Codes & Information Theory (yeh "code" hai kya).

Step 1 — Code kya hota hai? Haan/nahi sawaalon ka ek tree

KYA. Hum har prefix-free code ko ek binary tree ke roop mein draw karte hain. Upar se shuru karo (root se). Left jaana matlab 0 likhna; right jaana matlab 1 likhna. Har symbol ek leaf par rehta hai (ek bottom node jiske koi children nahi hote). Uska codeword root se neeche uske tak ke turns ka sequence hota hai.

Tree kyun, list kyun nahi? Kyunki "prefix-free" ka matlab bilkul yahi hai ki "har symbol ek leaf hai." Agar koi symbol ek internal node par hota, toh uski bit-string uske neeche ki har cheez ka prefix hoti — ambiguous. Tree prefix rule ko automatic aur visible bana deta hai.

PICTURE. Neeche, amber path root→left→right→left follow karo: isse codeword 010 banta hai. Koi symbol us path par apne ekdum end ke alawa nahi baitha hai.

Figure — Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm)

Step 2 — Hum kya minimize kar rahe hain? Total bits bhejna

KYA. Yeh saare symbols ke liye joḍo. Woh total hi woh number hai jise hum chhhota karna chahte hain: $Cost = \sum_{i} how often symbol i appears f_{i} \times bits in its codeword ℓ_{i}$

Yeh formula kyun, sirf "shortest codewords" kyun nahi? Kyunki ek rare symbol jiske paas lamba codeword hai, zyada hurt nahi karta (chhota $f_{i}$ ), jabki ek common symbol jiske paas lamba codeword hai woh disaster hai (bada $f_{i}$ ). Product $f_{i} ℓ_{i}$ trade-off ko bilkul sahi capture karta hai: yeh woh total bandwidth hai jo yeh symbol khaata hai.

PICTURE. Neeche, har leaf ka column $f_{i}$ (ek bar) times $ℓ_{i}$ (uski depth) dikhata hai. Message cost shaded areas ka sum hai — hum sabse chhota total shaded area chahte hain.

Step 3 — Cost count karne ka ek cleaner tarika: internal nodes ka sum

KYA. Bilkul same Cost compute karne ka ek doosra tarika hai, aur yahi proof ki key hai. Har internal node (ek node jiske children hain) ko uske neeche ki saari leaf-frequencies ka sum barabar ek frequency do. Claim: $Cost = \sum_{internal nodes v} total frequency of leaves under v g_{v}$

YEH SACH KYUN HAI? Kisi bhi single leaf $i$ ko dekho depth $ℓ_{i}$ par. Root se use reach karne ke liye aap exactly $ℓ_{i}$ internal nodes se guzarte ho (har edge ke liye ek). Toh $f_{i}$ un $ℓ_{i}$ internal-node sums mein se har ek mein ek baar count hota hai. Total times $f_{i}$ count hota hai $= ℓ_{i}$ . Yahi exactly $f_{i} ℓ_{i}$ hai — pehle jaisa hi contribution. Saari leaves par sum karne se same Cost milti hai, bas alag tarike se bookkeep ki gayi.

PICTURE. Amber leaf ki frequency tree ke upar flow karti hai; har internal node jisse woh guzarti hai, uski running total mein woh frequency add hoti hai. Upar ke arrows ginlo: yahi depth hai.

Cost identity ka reading

Total bits = internal nodes par (us node ke neeche combined frequency) ka sum, kyunki har symbol ki frequency depth ke har level par ek baar count hoti hai.

Step 4 — Greedy move: do sabse chhhote joḍo, aur recurse karo

KYA. Saare $n$ symbols ko frequency ke hisaab se ek min-heap mein daalo. Repeat karo: do sabse chhhote pop karo, $a$ aur $b$ ; frequency $f_{a} + f_{b}$ aur children $a, b$ ke saath ek naya node banao; ise wapas push karo. $n - 1$ merges ke baad ek node bachta hai — root.

Do sabse chhhote kyun? Step 3 ne kaha ki har merge apni combined frequency Cost mein charge karta hai. Running bill kam rakhne ke liye, har merge ko do sabse sasti available frequencies combine karni chahiye. Saath hi, jo bhi do hum pehle merge karte hain woh final tree mein sabse gehre leaves ban jaate hain (har baad wala merge unhe aur neeche push karta hai) — toh sabse chhoti frequencies theek se sabse gehre jagah pahunchti hain, Step 2 ki tension se match karti hui.

PICTURE. Ek merge dekho: do sabse chhote bars (amber) heap se nikalte hain aur ek lamba bar ban ke wapas aate hain; heap reorder hoti hai.

Step 5 — YEH OPTIMAL KYUN HAI: exchange picture

Yahi heart hai. Hum ek Exchange Argument use karte hain: koi bhi optimal tree lo aur dikhao ki hamari greedy choice use kabhi worse nahi banati.

KYA. Maano $a, b$ do sabse kam frequency wale symbols hain. Koi bhi optimal tree $T^{⋆}$ lo. Usme kaheen, sabse gehre level par, do sibling leaves baithti hain — unhe $x, y$ kaho (ek well-formed code tree mein sabse gehre node ka sibling hamesha hota hai). Ab swap karo: $a$ ko $x$ ki jagah neeche le jao aur $x$ ko $a$ ki jagah upar le jao; same $b, y$ ke liye.

SWAP HURT KYUN NAHI KAR SAKTA. $a$ (frequency $f_{a}$ , purani depth $d_{a}$ ) aur $x$ (frequency $f_{x}$ , purani depth $d_{x}$ ) swap karna consider karo. Sirf yeh do leaves depth change karti hain, toh Cost change hai: $Δ = \leq 0 since a is a smallest freq (f_{a} - f_{x}) \times \geq 0 since x is deepest (d_{x} - d_{a}) \leq 0$

$f_{a} - f_{x} \leq 0$ : $a$ do sabse chhoti frequencies mein se ek hai, toh woh $\leq f_{x}$ hai.
$d_{x} - d_{a} \geq 0$ : $x$ sabse gehre level par hai, toh woh $\geq$ kisi bhi aur depth se hai.
Non-positive times non-negative non-positive hota hai — swap Cost increase nahi kar sakta.

Toh ek optimal tree exist karti hai jisme $a, b$ sabse gehre siblings hain — bilkul wahi pair jise hamara greedy step merge karta hai. Greedy safe hai. Phir $a, b$ delete karo, unke parent ko frequency $f_{a} + f_{b}$ wala naya leaf treat karo, aur wahi argument chhoti problem par chalata hai (optimal substructure) jab tak tree build na ho jaye. $□$

PICTURE. Left: ek optimal tree jisme ek frequent symbol deep mein fansa hai aur ek rare wala shallow mein. Right: swap ke baad, rare wala deep hai, frequent wala shallow — amber Cost bar shrink hoti hai ya tie hoti hai, kabhi barhti nahi.

Step 6 — Edge aur degenerate cases

Har scenario cover hona chahiye, warna reader usi ek par trip kar jaata hai jise aapne skip kiya.

Definition Corner cases, har ek resolved

Ek symbol ( $n = 1$ ). Koi merge nahi hota. Convention: use single codeword 0 do (length 1). Cost $= f_{1} \cdot 1$ . Ek leaf wale tree ki depth-1 by convention hoti hai taaki file zero-length-encoded na ho.
Do symbols ( $n = 2$ ). Ek merge: 0 aur 1, har ek length 1. Cost $= f_{1} + f_{2}$ (unki combined frequency = single internal node). Trivially optimal.
Frequency mein ties. Heap equal-frequency items mein se koi bhi pehle pop kar sakti hai. Alag tie-breaks se alag trees milte hain par identical Cost — Step-5 ki inequality ne sirf $\leq$ use kiya, toh ties optimality nahi todtein.
Ek dominant symbol (ek $f_{i}$ baaki sab se bada). Yeh sabse baad mein merge hota hai, depth 1 par end hota hai jiske codeword ki length 1 hai — sabse frequent symbol ke liye bilkul theek.
Zero-frequency symbol. Ise fir bhi ek codeword chahiye; yeh pehle merge hota hai (smallest), sabse gehre land karta hai, Cost mein $0$ contribute karta hai. Harmless.

PICTURE. Do extreme skylines side by side: ek balanced tree (saari frequencies near-equal → near-equal depths) aur ek skewed tree (ek badi frequency → ek lamba patla comb). Dono apni frequencies ke liye Huffman-optimal hain.

Ek-picture summary

Sab ek saath: heap sabse chhote pair ko merge mein bhejta hai, merge apni combined frequency Cost tally mein add karta hai, tree neeche barhta hai, aur exchange argument guarantee karta hai ki sabse chhoti frequencies sabse gehre end hoti hain — toh total shaded Cost utni chhoti hai jitni kisi bhi tree mein ho sakti hai.

Recall Feynman: poora walkthrough apne shabdon mein batao

Socho tum words ke liye chhote secret-codes invent kar rahe ho. Code bas left/right turns ka ek tree hai, aur har word neeche baithta hai — ek leaf mein. Koi word kitna deep hai = uska code kitna lamba hai (Step 1). Tum fewest total bits bhejna chahte ho, isliye har word ke liye "kitni baar × kitna lamba" pay karte ho aur joḍ lete ho (Step 2). Trick yeh hai: wahi total tree mein har branch-point ki sizes joḍne ke barabar hai — kyunki har word ka count har level par ek baar tally hota hai jis par woh root ke neeche baitha hai (Step 3). Toh bill kam rakhne ke liye, jab bhi do words ko branch mein fuse karo, do rarest wale fuse karo — sabse sasta possible fusion — aur woh do neeche sink ho jaate hain, sabse lambe codes paate hain (Step 4). Rarest-pakadna hamesha optimal kyun hai? Koi bhi best-possible tree lo; do rarest words bottom par nahi bhi ho sakte hain, lekin agar tum unhe swap karke wahan le jaao, tum chhote numbers ko gehre le ja rahe ho aur bade numbers ko upar kheench rahe ho — yeh sirf bits bacha sakta hai, kabhi waste nahi kar sakta (Step 5). Chhote cases handle karo (ek word, do words, ties, ek giant word) aur ho gaya (Step 6). Frequent words ko chhote codes milte hain, rare words ko lambe wale, aur koi arrangement ise beat nahi kar sakti.