ערימת פיבונאצ'י – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שדדשכ (שיחה | תרומות)
אין תקציר עריכה
שורה 1:
#redirectב[[ערימה#מדעי המחשב]], '''ערימת פיבונאצ'י''' היא סוג של [[מבנה נתונים|מבנה הנתונים]] [[ערימה]].
 
==מבוא==
ערימה היא מבנה נתונים המשמשת למספר דברים, למשל, [[תור עדיפויות]]. היא מאפשרת לבצע במהירות הכנסה, מציאת מינימום, מחיקה והקטנת הערך. [[ערימה בינומית]], הממומשת כאוסף [[עץ בינומי|עצים בינומיים]], מאפשרת גם למזג במהירות שתי ערימות.
 
עם זאת, לעיתים נדרש שיפור נוסף בערימה: פעולת "הקטנת ערך" מבוצעת בזמן <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(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>.
 
{{מבני נתונים}}
 
[[קטגוריה:ערימה|פיבונאצ'י]]
[[קטגוריה:סדרת פיבונאצ'י]]