Binomial Heap ใน C++ (โครงสร้างข้อมูล Binomial Heap)

ภาพรวม

Binomial Heap เป็นขยายของ Binary Heap ที่รองรับการ Merge/Union ได้เร็วขึ้น (O(log n)) พร้อมรักษา Operation อื่นๆ ของ Binary Heap

Binomial Tree คืออะไร?

Binomial Tree ของ Order k สร้างจากการนำ Binomial Tree Order k-1 สองต้น มารวมกัน โดยทำให้ต้นหนึ่งเป็น Leftmost Child ของอีกต้น

คุณสมบัติของ Binomial Tree Order k:

• จำนวนโหนด = 2^k
• ความลึก (Depth) = k
• จำนวนโหนดที่ Depth i = C(k, i) (Binomial Coefficient)
• Root มี Degree = k และ Children เป็น Binomial Trees Order k-1, k-2, ..., 0 (จากซ้ายไปขวา)

Binomial Heap

Binomial Heap คือ Collection ของ Binomial Trees ที่:

1. แต่ละ Tree เป็น Min Heap (Root มีค่าน้อยที่สุดใน Tree นั้น)
2. ไม่มี Tree ใดมี Degree เท่ากัน (สูงสุด 1 Tree ต่อ Degree)

ความสัมพันธ์กับ Binary Representation

Binomial Heap ที่มี n โหนด จะมีจำนวน Binomial Trees เท่ากับ จำนวน Set Bits ใน Binary Representation ของ n

ตัวอย่าง: n = 13 (Binary: 1101) มี 3 Set Bits → มี 3 Binomial Trees (Order 0, 2, 3)

จำนวน Trees สูงสุด = O(log n)

Operations หลัก

โครงสร้าง Node (C++)

struct BinomialNode {
    int key;
    int degree;
    BinomialNode *parent, *child, *sibling;
    BinomialNode(int k) : key(k), degree(0), parent(nullptr), child(nullptr), sibling(nullptr) {}
};

Union Operation ( 핵심 )

Union ทำงานโดยการ Merge Root Lists ของ 2 Heaps ตาม Degree แล้ว Fix Violation (Degree ซ้ำ) โดย:

1. Merge Root Lists สองอันเรียงตาม Degree
2. เดินผ่าน List ถ้าเจอ 3 ต้นติดกัน Degree เท่ากัน → รวม 2 ต้นแรก
3. ถ้าเจอ 2 ต้นติดกัน Degree เท่ากัน → รวมทั้งคู่

คำอธิบายเพิ่มเติม

• Binomial Heap ใช้ใน Priority Queue ที่ต้องการ Merge บ่อย
• Fibonacci Heap เป็นการพัฒนาต่อที่ทำให้ DecreaseKey/Insert เป็น O(1) Amortized
• ในทางปฏิบัติ Binary Heap (Priority Queue) ใช้ง่ายกว่าและเร็วกว่าสำหรับกรณีทั่วไป

ภาพสรุป Binomial Heap 12 โหนด

        10                  15
       /  \                / | \
      12  15              18 20 25
     / \  / \            / \
    14 20 18 25         22  30
   (Order 2)           (Order 3)
   
Total: 2^2 + 2^3 = 4 + 8 = 12 nodes

ZigZag Conversion ใน C++ (แปลง String เป็นรูป ZigZag)

การแปลง Binary Tree เป็น Binary Search Tree ด้วย STL Set ใน C++