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

**ฟีโบนัชชีฮีป** () เป็นโครงสร้างข้อมูลชนิดหนึ่งที่พัฒนามาจากฮีป ซึ่งมีประสิทธิภาพในการทำงานที่ดีกว่าฮีปทวิภาค (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*&nbsp;+&nbsp;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

## ประสิทธิภาพ

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

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

## แหล่งข้อมูลอื่น
* ตัวอย่างการใช้งาน Fibonacci Heap 

หมวดหมู่:ฮีป (โครงสร้างข้อมูล)
หมวดหมู่:จำนวนฟีโบนัชชี