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

จากวิกิพีเดีย สารานุกรมเสรี
Jump to navigation Jump to search

ฟีโบนัชชีฮีป (อังกฤษ: 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 จะมีขนาดอย่างน้อย Fk + 2, เมื่อ Fk คือจำนวนฟีโบนัชชีลำดับที่ 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 เป็นขนาดข้อมูล

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

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