ฮีปฟีโบนัชชี

โครงสร้าง

ฟีโบนัชชีฮีป เป็นโครงสร้างข้อมูลที่มีการใช้ต้นไม้เหมือนกับ แถวคอยลำดับความสำคัญ (priority queue) โดยมีการเก็บข้อมูลแบบฮีปน้อยสุด โดยมีลักษณะที่สำคัญคือปมพ่อ (parent node) จะมีความสำคัญน้อยกว่าปมลูก (child node) ทำให้ข้อมูลที่มีความสำคัญน้อยที่สุดจะอยู่ที่ปมราก (root) เสมอ
การจัดเก็บข้อมูลของฟีโบนัชชีฮีปจะมีความยืดหยุ่นมากกว่าBinary Heap โดยฮีปชนิดนี้ไม่ได้กำหนดรูปร่างไว้อย่างชัดเจน ทำให้ในบางกรณีข้อมูลทั้งหมดอาจจะกระจายอยู่ในต้นไม้คนละต้น (Separate tree) หรืออาจรวมอยู่ในต้นไม้ต้นเดียวที่มีความลึก N ก็ได้ จากการที่มีความยืดหยุ่นมากทำให้บางคำสั่งมีการทำงานแบบขี้เกียจ (Lazy manner) คือ ในหลายคำสั่งที่มีการเรียกใช้บ่อยครั้งมีการทำงานแบบลวกๆ เพื่อประหยัดเวลา แต่ทำให้เมื่อมีการเรียกบางคำสั่งที่ใช้งานไม่บ่อยนัก จะต้องมีการสะสางงานที่ไม่ได้ทำเหล่านั้นก่อน ทำให้เสียเวลาในการทำงานมากขึ้น แต่เมื่อมองในภาพรวมแล้วจะได้การทำงานที่เร็วขึ้น เนื่องจากสามารถใช้คำสั่งที่ใช้งานมากได้อย่างรวดเร็ว ในขณะที่คำสั่งที่ถูกเรียกน้อยๆจะทำงานช้าลงบ้างก็ไม่เสียหาย
คุณสมบัติที่ควรกล่าวของฮีปแต่ละตัว คือ ความเร็วในการทำงาน โดยเฉพาะองศาของปม (Degrees of Nodes) ซึ่งในที่นี้คือจำนวนปมลูก จะถูกเก็บไว้ค่อนข้างน้อย โดยแต่ละปมจะมี degree ไม่เกิน O (log (n)) และต้นไม้ย่อย (subtree) ที่อยู่ในปมที่มี degree k จะมีขนาดอย่างน้อย Fₖ + 2, เมื่อ Fₖ คือจำนวนฟีโบนัชชีลำดับที่ k ทำให้เราสามารถตัดปมลูกออกมาปมที่ไม่ใช่ปมราก เมื่อปมถูกตัดออกจากปมแม่ก็จะนำไปสร้างเป็นต้นไม้ต้นใหม่ โดยจำนวนต้นไม้จะลดลงเมื่อทำคำสั่งลบข้อมูลตัวน้อย เพราะจะมีการเชื่อมต้นไม้แต่ละต้นเข้าด้วยกัน
เนื่องจากความที่เป็นโครงสร้างข้อมูลที่มีความยืดหยุ่นมาก ทำให้บางคำสั่งใช้เวลามากในขณะที่อีกหลายคำสั่งทำงานได้อย่างรวดเร็ว โดยในการวิเคราะห์เราจะสมมติว่าคำสั่งที่ทำงานเร็วจะใช้เวลามากกว่าที่ใช้จริงเล็กน้อย เพื่อนำเวลาส่วนเกินนี้ไปหักออกเมื่อมีการเรียกคำสั่งที่ใช้เวลามาก โดยเวลาส่วนเกินนี้สามารถหาได้จาก potential function โดย potential function ของฟีโบนัชชีฮีป คือ
Potential = t + 2m, เมื่อ t = จำนวนต้นไม้ และ m = จำนวนปมที่ทำเครื่องหมาย
โดยปมจะถูกทำเครื่องหมายถ้ามีปมลูกอย่างน้อยหนึ่งปมถูกตัดออก (ปมรากจะไม่มีการทำเครื่องหมาย)

การทำงานในแต่ละคำสั่ง

การเชื่อมโยงปมรากจะใช้วิธีแบบ circular doubly linked list เพื่อที่จะได้ลบและเชื่อมโยงปมต่างๆ ได้อย่างรวดเร็ว นอกจากนี้ยังสามารถกำหนดจำนวนของปมลูกหรือตรวจสอบว่ามีการทำเครื่องหมายอยู่หรือไม่ ยิ่งไปกว่านั้นยังสามารถสร้างตัวชี้ (Pointer) ไปยังปมรากที่มีค่าน้อยสุดได้

ค้นข้อมูลตัวน้อย (Find minimum)

คำสั่งค้นข้อมูลตัวน้อย สามารถทำได้ง่าย เพราะไม่ต้องเปลี่ยนโครงสร้างในฮีป และมีตัวชี้ไปยังปมรากที่น้อยที่สุดอยู่แล้ว ดังนั้นจึงใช้เวลาเป็นค่าคงตัว (O (1))

ผสาน (Merge)

คำสั่งผสาน สามารถทำได้โดยการรวม list ปมรากของฮีปทั้งสองเข้าด้วยกันและ pontential ไม่เปลี่ยน ดังนั้นจึงใช้เวลาคงตัว (O (1))

เพิ่มข้อมูล (Insert)

คำสั่งเพิ่มข้อมูล สามารถทำได้โดยสร้างฮีปใหม่ที่มีข้อมูลอยู่ 1 ตัว คือข้อมูลที่ต้องการเพิ่มจากนั้นจึงนำมาผสานกับฮีปเก่า ทำให้มีต้นไม้และ potential เพิ่มขึ้นอีกหนึ่ง แต่ไม่ส่งผลกับเวลาทำงาน ดังนั้นจึงใช้เวลาคงตัว (O (1))

ลด key (Decrease Key)

คำสั่งลด key เมื่อทำคำสั่งนี้ จะทำให้โครงสร้างของฮีปผิด (ข้อมูลตัวน้อยเป็นปมลูกของข้อมูลตัวมาก) ปมนั้นจะถูกตัดออก ถ้าปมพ่อไม่ใช่ปมราก ปมนั้นจะถูกทำเครื่องหมาย ถ้าปมนั้นถูกทำเครื่องหมายอยู่แล้ว ปมนั้นจะถูกตัดพร้อมกับทำเครื่องหมายที่ปมพ่อ จากนั้นเราจะไล่ขึ้นไปจนกว่าจะเจอปมรากหรือปมที่ไม่ได้ทำเครื่องหมาย โดยการทำเช่นนี้ จะสร้างต้นไม้ใหม่ k ต้น และทำให้ potential ลดลงอย่างน้อย k - 2 เวลาที่ใช้ในการตัดจะเท่ากับ O (k) ซึ่งหมายความว่าใช้เวลาคงตัว (O (1))

ลบข้อมูล (Delete)

คำสั่งลบข้อมูล ทำได้โดยเปลี่ยนค่าของข้อมูลที่ต้องการลบให้มีค่าน้อยๆ (โดยทั่วไป คือ เปลี่ยนเป็น -∞) จะทำให้ข้อมูลตัวนั้นถูกปรับเป็นข้อมูลน้อยสุด จากนั้นจึงทำการลบข้อมูลตัวน้อย ก็จะสามารถลบข้อมูลที่ต้องการได้ ซึ่งการทำงานจะใช้เวลาทั้งหมด O (log (n))

กรณีเลวร้ายที่สุด

แม้ว่าการทำงานโดยส่วนใหญ่จะสามารถทำได้อย่างรวดเร็ว แต่ก็มีคำสั่งบางคำสั่งที่ใช้เวลาในการทำงานนาน ดังนั้นฟีโบนัชชีฮีปจึงไม่เหมาะกับงานที่ต้องทำงานกับระบบแบบ Real-time