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

ฟีโบนัชชีฮีป (อังกฤษ: Fibonacci Heap) เป็นโครงสร้างข้อมูลชนิดหนึ่งที่พัฒนามาจากฮีป ซึ่งมีประสิทธิภาพในการทำงานที่ดีกว่าฮีปทวิภาค (Binary Heap) ถูกคิดค้นในพ.ศ. 2527 (ค.ศ. 1984) และได้รับการเผยแพร่ออกมาในปี พ.ศ. 2530 โดยมีการใช้จำนวนฟีโบนัชชีในการวิเคราะห์ขณะทำงาน (Running time analysis) ซึ่งเป็นที่มาของชื่อฟีโบนัชชีฮีป

โครงสร้าง

ฟีโบนัชชีฮีป เป็นโครงสร้างข้อมูลที่มีการใช้ต้นไม้เหมือนกับ แถวคอยลำดับความสำคัญ (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_k + 2, เมื่อ F_k คือจำนวนฟีโบนัชชีลำดับที่ 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))

ลบข้อมูลตัวน้อย (Extract min)

คำสั่งลบข้อมูลตัวน้อย จะแบ่งเป็น 3 ขั้นตอนย่อย

• ขั้นแรกจะทำการลบข้อมูลตัวน้อยออก ปมลูกจะกลายเป็นต้นไม้ใหม่ ถ้ามีปมลูกทั้งหมด d ปม จะใช้เวลา O (d) เพื่อเพิ่มปมลูกเป็นปมรากและทำให้ potential ลดลง d - 1 ดังนั้นจะใช้เวลาในขั้นตอนนี้ O (d) = O (log (n))
• ขั้นที่สองต้องทำการหา pointer มาชี้ยังปมรากน้อยสุด โดยในขณะนี้อาจมีปมมากถึง n ปม ดังนั้นจึงต้องทำการลดปมราก โดยถ้าปมราก 2 ปมมี degree เท่ากัน เราจะรวมทั้งสองปมเป็นต้นไม้ต้นเดียว โดยให้ปมน้อยเป็นปมราก ซึ่งวิธีนี้จะทำให้มี degree เพิ่มขึ้น 1 โดยเราจะทำเช่นนี้จนกว่าจะไม่มีปมรากใดๆ ที่มี degree เท่ากัน โดยจะใช้ Array ในการค้นหาปมรากที่มี degree ต่างกัน โดยสร้าง Array ความยาว O (log (n)) โดยให้แต่ละช่องของArrayเก็บตัวชี้ไปยังต้นไม้ที่มี degree ต่างๆ ถ้าหากพบต้นไม้ที่มี degree เท่ากัน ก็ทำการรวมต้นไม้และปรับค่า Array ใหม่ โดยจะใช้เวลาในขั้นตอนนี้ คือ O (log (n) + m) เมื่อ m เป็นจำนวนปมรากตอนเริ่มขั้นตอนนี้ และเมื่อเสร็จจะมีปมรากทั้งหมด O (log (n)) เนื่องจากทุกปมมี degree ต่างกันหมด ดังนั้น potential จะเปลี่ยนแปลงไป O (log (n)) - m และใช้เวลาในขั้นนี้ คือ O (log (n) + m) + O (log (n)) - m = O (log (n))
• ขั้นที่สาม คือ ทำการตรวจสอบปมรากเพื่อหาปมน้อยสุดเพื่อที่จะได้ชี้ pointer ไปยังปมน้อยสุด โดยขั้นตอนนี้ใช้เวลา O (log (n))

เมื่อรวมเวลาทั้งสามขั้นตอนจะใช้เวลาทั้งหมดเท่ากับ O (log (n))

ลด key (Decrease Key)

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

ลบข้อมูล (Delete)

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

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

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

ประสิทธิภาพ

โครงสร้างข้อมูล	เพิ่มข้อมูล	ค้นข้อมูลตัวน้อย	ลบข้อมูลตัวน้อย	ลด key	ลบข้อมูล	ผสาน
ฟีโบนัชชีฮีป	O (1)	O (1)	O (log (n))	O (1)	O (log (n))	O (1)

เมื่อ n เป็นขนาดข้อมูล

ดูประสิทธิภาพการทำงานเทียบกับฮีปชนิดอื่นได้ ที่นี่

แหล่งข้อมูลอื่น

• ตัวอย่างการใช้งาน Fibonacci Heap เก็บถาวร 2011-02-01 ที่ เวย์แบ็กแมชชีน