ערימת פיבונאצ'י היא סוג של ערימה שהומצא מייקל פרדמן ורוברט טרג'אן. ערימה היא מבנה נתונים שמשמש למשל כתור עדיפויות. היא מאפשרת הכנסה מהירה, מציאת מינימום, מחיקה והקטנת ערך (הקטנה של ערך קיים במבנה).
בכמה אלגוריתמים, כמו דייקסטרה (אלגוריתם למציאת מסלול הקצר בגרף), מבצעים הרבה פעולות הקטנת ערך. בערימה בינומית עלות ההקטנה היא גבוהה יחסית, ולכן פותחה ערימת פיבונאצ'י כדי לשפר זאת. בערימת פיבונאצ'י סדרת פעולות הקטנת ערך רבות עולה בסך הכל פחות, מה שמקצר את זמן הריצה של דייקסטרה ל-O(m + n log n).
המימוש דומה לערימה בינומית: אוספים כמה עצים שכל אחד שומר את כלל הערימה, ערך כל צומת לא גדול מערכי ילדיו. שורשי העצים מאוחזקים ברשימה מקושרת דו־כיוונית, ויש מצביע לשורש המינימלי כדי להחזיר אותו בזמן קבוע.
כדי לשמור על גבולות גדלים מהירים, דרגת צומת (מספר ילדיו) מוגבלת בערך בלוגריתמי של n. גודל תת־עץ של שורש בעל דרגה k הוא לפחות ערך מסדרת פיבונאצ'י המתאים, ומכאן השם "פיבונאצ'י". כשכורתים (cut) תת־עץ מהאב, מסמנים צמתים; אם חותכים צומת מסומן פעם נוספת, גם הוא נכרת מהאב שלו. סימון זה שומר על הגבלות הגדלים.
הפעולות העיקריות הן: הכנסת איבר, מציאת מינימום, מחיקת המינימום והקטנת ערך. מחיקת המינימום כוללת איחוד שורשים דומים. הקטנת הערך עשויה לחתוך תתי־עצים ולעדכן סימונים.
מנתחים את העלות בעזרת פונקציית פוטנציאל. הפוטנציאל מוגדר כמספר העצים ועוד פעמיים מספר האיברים המסומנים. העלות הגרועה ביותר של מחיקת מינימום היא ליניארית, אך העלות השיעורית (amortized) שלה היא O(log n) בגלל האיחודים והירידה בפוטנציאל.
עבור הקטנת ערך העלות הגרועה ביותר גם כן יכולה להיות ליניארית. עם זאת, בסדרה של k חיתוכים עוקבים הפוטנציאל יורד במידה שמדגימה שהעלות השיעורית לכל פעולה היא קבועה. כלומר הקטנת ערך היא amortized O(1).
Quake Heap מוזכר כמח替ה אפשרית לערימת פיבונאצ'י. הוא מציע חלופה שונה למימוש ולניתוח הפעולות.
ערימת פיבונאצ'י היא סוג של ערימה. ערימה היא מבנה נתונים לשמירת דברים לפי סדר.
היא עוזרת לעשות פעולות כמו הוספה, מציאת הקטן ביותר והורדת ערך. הורדת ערך פירושה להקטין את הערך של פריט שכבר בערימה.
מבנה זה מייעל עבודות כמו דייקסטרה. דייקסטרה הוא דרך למצוא את הדרך הקצרה ברשת.
המבנה בנוי מאוסף עצים. בכל עץ הערכים של ההורים לא גדולים מהילדים. שורשי העצים נשמרים ברשימה מיוחדת ויש מצביע לשורש עם הערך הקטן ביותר.
השיטה נקראת על שם סדרת פיבונאצ'י כי תת־העצים מקבלים גדלים שקשורים לסדרה הזו.
כשתורקים (קוטעים) תת־עץ, מסמנים צמתים. אם חותכים שוב צומת מסומן, מקטעים גם אותו.
פועלים: הכנסת פריט, מציאת המינימום, מחיקה והקטנת ערך. מחיקת המינימום מאחדת עצים.
למרות שפעולה אחת יכולה לקחת הרבה זמן, בסדרה של פעולות הזמן הממוצע לכל פעולה קטן. זה מה שמקנה ערימת פיבונאצ'י יתרון בזמן לחיפוש דרכים ולבעיות דומות.
תגובות גולשים