อัลกอริทึมง่ายๆ (Binary Huffman)
- เตรียม n Initial Huffman Trees (แต่ละตัว = Single Leaf Node) ใส่ Priority Queue เรียงตาม Weight (Frequency)
- Dequeue 2 ตัวที่ Weight น้อยสุด → Combine → New Tree: Root มี 2 Children, Weight = Sum ของ Children
- Enqueue New Tree กลับ Priority Queue
- Repeat 2-3 จนเหลือ 1 Tree
Greedy Algorithm: ทุก Iteration Merge 2 Subtrees Weight น้อยสุด
Correctness Proof
Lemma: x, y = 2 ตัวที่ Frequency น้อยสุด → มี Optimal Code Tree ที่ x, y เป็น Siblings และ Depth น้อยที่สุดเท่ากับ Leaf อื่นๆ
Theorem: Huffman Codes = Optimal Prefix-free Binary Codes (Greedy Algorithm สร้าง Tree ที่ Minimum External Path Weight)
การขยายเป็น t-ary Trees (t > 2)
Generalization: Merge t ตัว** ที่ Weight น้อยสุดแทน 2 ตัว
- Priority Queue ของ n Trees (Leaves)
- Dequeue t ตัว Weight น้อยสุด → Combine → New Node มี t Children, Weight = Sum
- Enqueue กลับ
- Repeat จนเหลือ 1 Tree
เงื่อนไข: Dummy Nodes
เพื่อให้ Merge t ตัวได้ทุก Step: (n - 1) mod (t - 1) = 0
ถ้าไม่เป็น → เพิ่ม Dummy Nodes (Weight = 0) จนกว่าเงื่อนไขจะตรง
ตัวอย่าง: t = 3 (Ternary Huffman)
n = 5 → (5-1) mod 2 = 0 ✓ ไม่ต้อง Dummy
n = 6 → (6-1) mod 2 = 1 → เพิ่ม 1 Dummy Node
สรุป
t-ary Huffman = Generalization ของ Binary Huffman ใช้ Priority Queue Merge t ตัวต่อรอบ
ต้องเพิ่ม Dummy Nodes เพื่อให้ (n-1) mod (t-1) = 0
Optimal Prefix-free t-ary Codes ได้จาก Greedy Approach เดียวกัน
