הצגת המקור של הדף "ערימת פיבונאצ'י"

ב[[מדעי המחשב]], '''ערימת פיבונאצ'י''' היא סוג של [[מבנה נתונים|מבנה הנתונים]] [[ערימה]] שהומצא על ידי מייקל פרדמן ו[[רוברט טרג'אן]]<ref>{{צ-מאמר|מחבר=Michal L. Fredman, Robert Endre Tarjan|שם=Fibonacci heaps and their uses in improved network optimization algorithms|קישור=https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/fibonacci%20heaps.pdf}}</ref>.

==מבוא==
ערימה היא מבנה נתונים המשמשת למספר דברים, למשל, [[תור עדיפויות]]. היא מאפשרת לבצע במהירות הכנסה, מציאת מינימום, מחיקה והקטנת הערך. [[ערימה בינומית]], הממומשת כאוסף [[עץ בינומי|עצים בינומיים]], מאפשרת גם למזג במהירות שתי ערימות.

עם זאת, לעיתים נדרש שיפור נוסף בערימה: פעולת "הקטנת ערך" מבוצעת בזמן <math>O(\log n)</math>, בעוד שפעמים רבות פעולה זו נפוצה יותר מהאחרות ומבוצעת פעמים רבות. דוגמה לכך היא [[אלגוריתם דייקסטרה]] המשמש למציאת מסלול מינימלי ב[[גרף ממושקל]]: אם בגרף יש n קודקודים ו-m קשתות, יש לשמור בערימה n איברים שייצגו את הקודקודים, ולבצע עליהם m פעולות הקטנת הערך ו-n פעולות מחיקה. משום כך זמן הריצה ב[[ערימה בינארית]] יהיה <math>O(m\log n)</math> אך מאחר ש-m>n, היינו מעדיפים לחסוך בזמן העלות של פעולת הקטנת הערך.

ערימת פיבונאצ'י משמשת למטרה זאת. היא גמישה יותר והמבנה בה פחות קבוע ובשל כך פעולה בודדת יכולה לקחת יותר זמן מבערימה בינומית רגילה, אך יתרונה הוא בכך ש[[ניתוח לשיעורין|העלות לשיעורין]] שלה, כלומר זמן הריצה של סדרת פעולות - קטן יותר. כך לדוגמה זמן הריצה של n פעולות "הקטנת הערך", שכל אחת מהן לוקחת <math>O(n)</math> במקרה הגרוע, לוקח <math>O(n)</math> בלבד לכולן (בממוצע, <math>O(1)</math> לכל פעולה). וכך זמן הריצה של אלגוריתם דייקסטרה יורד ל-
<math>O(m+n\log n)</math>.

==מימוש==
[[קובץ:Fibonacci heap.png|שמאל|ממוזער|ערימת פיבונאצ'י]]
בדומה לערימה בינומית, ערימת פיבונאצ'י ממומשת באמצעות אוסף [[עץ (תורת הגרפים)|עצים]]. כל אחד מהעצים מקיים את "כלל הערימה" - ערך כל קודקוד לא גדול מערכי בניו. את השורשים של העצים מחזיקים ב[[רשימה מקושרת]] דו כיוונית (כלומר עם מצביעים קדימה ואחורה). בנוסף, שומרים מצביע לאיבר המינימלי כדי לאפשר את החזרתו ב-<math>O(1)</math>.

 יש מספר הגבלות שמבטיחות זמן ריצה מהיר: דרגת כל קודקוד (כלומר מספר ילדיו) היא לכל היותר <math>O(\log n)</math>, וגודל תת-עץ שדרגת השורש שלו היא k הוא לפחות כערך המספר ה-k+2 ב[[סדרת פיבונאצ'י]] (ומכאן השם). כדי לשמור על כללים אלה, דואגים שאם "כורתים" שני תתי-עצים (כלומר הופכים את השורשים שלהם לעצים חדשים בערימה) כורתים גם את אביהם (אלא אם כן הוא שורש) בעזרת סימון קודקודים. שיטה זאת מבטיחה חסם תחתון על גודל העצים, אולם היא מביאה למספר גדול של עצים; כדי לתקן זאת, בפעולה "מחיקת מינימום" (שתתואר להלן) דואגים לאחד חלק מהעצים.

===פעולות===
[[קובץ:Fibonacci heap extractmin1.png|שמאל|ממוזער|100px|אותה הערימה מיד אחרי מחיקת המינימום, לפני התיקון.]]
[[קובץ:Fibonacci heap extractmin2.png|שמאל|ממוזער|100px|אותה הערימה אחרי תיקון העץ.]]
[[קובץ:Fibonacci heap-decreasekey.png|שמאל|ממוזער|200px|הערימה העליונה לאחר הקטנת הערך של 9 ל-0. שלושה עצים חדשים נוספו.]]
* '''הכנסה, מיזוג''': בפעולות אלו בא לידי ביטוי המימוש ה"עצלני" של הערימה: הן ממומשות במהירות, במחיר של צעדים נוספים שידרשו לעשות פעולות אחרות. בפעולת ההכנסה פשוט מוסיפים את האיבר בהתחלה, ובפעולת המיזוג משרשרים את הערימות ליצירת ערימה שמורכבת משתיהן. פעולות אלו לוקחות <math>O(1)</math>.
* '''מחיקת מינימום''': בפעולה זאת ראשית יש למחוק את האיבר המינימלי ולהפוך את ילדיו לעצים חדשים, אותם יש למזג עם הערימה. אולם, כעת יש למצוא את המינימום החדש, פעולה העלולה לקחת בזמן הגרוע <math>O(n)</math>. משום כך מוסיפים בפעולה זאת גם את "תיקון הערימה": מאחדים עצים בעלי דרגה זהה לעץ חדש, על ידי הוספת השורש בעל הערך הגדול יותר כבן נוסף לשורש הקטן יותר. ממשיכים בפעולה זאת עד שלא נותרים עוד שני שורשים מאותה דרגה (כדי לעשות זאת באופן יעיל, מחזיקים [[מערך (מבנה נתונים)|מערך]] עם מצביעים לשורשים מהדרגות השונות, ולאחר מכן עוברים על השורשים האחרים ומאחדים אותם עם הדרגה המתאימה כפי שתואר לעיל). בסופו של דבר יש למצוא את המינימום החדש - ואת זאת עושים על ידי ריצה על השורשים, ב-<math>O(\log n)</math> (מאחר שיש לכל היותר עץ אחד מכל דרגה, והדרגות גדלות באופן [[גדילה מעריכית|מעריכי]] כמו סדרת פיבונאצ'י).
* '''הקטנת ערך''': בפעולה זאת מקטינים תחילה את הערך. אם הוא היה שורש, יש לבדוק האם מצביע המינימום עדיין נכון ואם לא - לתקן. אם לא, יש לבדוק האם אביו עדיין קטן ממנו או שווה לו. אם לא, "כורתים" את תת-העץ שזהו השורש שלו, כלומר הופכים אותו לעץ חדש בערימה. לאחר מכן, מסמנים את אביו (אלא אם כן הוא שורש). אם אביו כבר מסומן, גם הוא נכרת והופך לעץ חדש, ומסמנים גם את אביו. ממשיכים כך עד שמסמנים קודקוד שלא היה מסומן, או מגיעים לשורש.
* '''מחיקה''': את המחיקה ניתן לבצע על ידי הקטנת הערך ל-[[אינסוף|<math>-\infty</math>]] (כלומר קטן יותר מכל הערכים) ולאחר מכן מחיקת המינימום.

==ניתוח==
כדי לנתח את העלות לשיעורין של הפעולות, ננקוט ב[[שיטת הפוטנציאל]]. פונקציית הפוטנציאל תהיה מספר העצים, ועוד פעמיים מספר האיברים המסומנים.

העלות הגרועה ביותר של פעולת מחיקת המינימום היא <math>O(n)</math>. נחשב את העלות לשיעורין: בפעולה היקרה ביותר, שהיא איחוד העצים, על כל איחוד עצים אנחנו מקטינים באחד את הפוטנציאל, ועל כן העלות בסופו של דבר היא <math>O(\log n)</math> (הנובע מחיפוש העצים המתאימים). עדכון המינימום גם הוא ב-<math>O(\log n)</math> ועל כן מקבלים שהעלות לשיעורין היא <math>O(\log n)</math>.

העלות הגרועה ביותר של פעולת הקטנת הערך היא <math>O(n)</math>. נחשב את העלות לשיעורין: נניח והיו k קודקודים שנכרתו ברצף, כלומר כולם (למעט אולי הראשון) היו מסומנים ועכשיו כבר לא, ובנוסף האבא של האחרון אולי סומן, לכן מספר המסומנים קטן במספר שבין k ל-k-2. לעומת זאת, מספר העצים גדל ב-k ולכן הפוטנציאל ירד ב-<math>2(k-2)-k=k-4</math>. בוצעו k פעולות. סה"כ הזמן לשיעורין הוא <math>k-(k-4)=4</math> כלומר קבוע. לכן זמן הריצה לשיעורין הוא <math>O(1)</math>.

== Quake Heap ==
מבנה נתונים אשר משמש כחלופה לערימת פיבונאצ'י נקרא Quake Heap<ref>{{צ-מאמר|מחבר=Timothy M. Chan|שם=Quake Heaps: A Simple Alternative to Fibonacci Heaps|קישור=https://tmc.web.engr.illinois.edu/heap_ianfest.pdf}}</ref> בעל שלושת הפעולות הבאות:

* '''הכנסה:''' הכנסת איבר x אל ערימה S, פעולה זו לוקחת <math>O(1)</math>.
* '''מחיקת מינימום:'''  מחיקת האיבר המינימלי בערימה והחזרתו, פעולה זו לוקחת <math>O(\log n)</math>.
* '''הקטנת ערך:''' שינוי ערכו של איבר מסוים לערך אשר בהכרח קטן יותר מערכו הנוכחי, פעולה זו לוקחת <math>O(1)</math>.

== קישורים חיצוניים ==

* {{יוטיוב|6JxvKfSV9Ns|3=חלק ממיזם Summer of Math Exposition (#SOME)|שם=Fibonacci Heaps or "How to invent an extremely clever data structure|ערוץ=SithDev|אורך=29:42}}

==הערות שוליים==
{{הערות שוליים|יישור=ימין}}
{{מבני נתונים}}
[[קטגוריה:עצים (גרפים)]]
[[קטגוריה:ערימה|פיבונאצ'י]]
[[קטגוריה:סדרת פיבונאצ'י]]