Binomial Tree
Binomial Heap เป็นคอลเลกชันของ Binomial Trees ต้นไม้ไบนอมีอัล Bk นิยามแบบ Recursive:
- B0 ประกอบด้วยโหนดเดียว
- Bk ประกอบด้วย Bk-1 สองต้น ที่เชื่อมต่อกัน รากของหนึ่งเป็น Left-most child ของรากอีกต้น
ตัวอย่าง Binomial Heaps
คุณสมบัติของ Binomial Trees
- Bk มีโหนด 2ᵏ ตัว
- ความสูงของต้นไม้คือ k
- มีโหนดที่ความลึก i จำนวน exatamente C(k, i) สำหรับ i = 0 ถึง k
คุณสมบัติของ Binomial Heap
- แต่ละ Binomial Tree ใน H เป็น Heap-ordered (คีย์ของโหนด ≥ คีย์ของพาเรนต์)
- มี Binomial Tree ใน H สูงสุด 1 ต้น ที่รากมี Degree ใดๆ ก็ตาม
ตัวอย่าง Binomial Heap
Heap นี้ประกอบด้วย B0, B2, B3 มีโหนด 1, 4, 8 ตัวตามลำดับ รวม n = 13 รากของต้นไม้เชื่อมด้วย Linked List เรียงตาม Degree เพิ่มขึ้น
