ลักษณะของ Fibonacci Heaps
คล้ายกับ Binomial Heaps, Fibonacci Heaps เป็นคอลเลกชันของต้นไม้ (Trees) พัฒนามาจาก Binomial Heaps แต่ต่างกันตรงที่ ต้นไม้ใน Binomial Heaps เป็น Ordered Trees ในขณะที่ Fibonacci Heaps เป็น Rooted แต่ Unordered
โครงสร้างโหนด
- ตัวชี้ p[x] ชี้ไปยังพาเรนต์
- ตัวชี้ child[x] ชี้ไปยังลูกหนึ่งในลูกๆ
- ลูกๆ ถูกเชื่อมต่อกันเป็น Circular Doubly Linked List เรียกว่า Child List
- แต่ละลูก y มี left[y] และ right[y] ชี้ไปยังพี่น้องซ้ายและขวา
- ถ้า y เป็นลูกคนเดียว left[y] = right[y] = y
- ลำดับพี่น้องใน Child List เป็น Arbitrary (ไม่สำคัญ)
ตัวอย่าง Fibonacci Heap
Fibonacci Heap H นี้ประกอบด้วย 5 Fibonacci Heaps และ 16 โหนด เส้นที่มีหัวลูกศรแสดง Root List โหนดค่าต่ำสุดในลิสต์ถูกชี้โดย min[H] ซึ่งมีค่า 4
การประยุกต์ใช้
อัลกอริทึมที่เร็วที่สุดในเชิง Asymptotic สำหรับปัญหาเช่น Minimum Spanning Trees, Single Source Shortest Paths ใช้ Fibonacci Heaps เป็นสิ่งจำเป็น
