ערימת פיבונאצ'י

במדעי המחשב, ערימת פיבונאצ'י היא סוג של מבנה הנתונים ערימה שהומצא על ידי מייקל פרדמן ורוברט טרג'אן.

מבנה נתונים הדומה לערימה זו, נקרא ערימת רעידת אדמה (Quake Heap) ובה הדברים דומים, אך ישנה דרישה שמספר הקודקודים ברמה ה - i יהיו לכל היותר 3/4 ממספר הקודקודים שברמה הנוכחית (כולל).

מבוא

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

עם זאת, לעיתים נדרש שיפור נוסף בערימה: פעולת "הקטנת ערך" מבוצעת בזמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log n)} , בעוד שפעמים רבות פעולה זו נפוצה יותר מהאחרות ומבוצעת פעמים רבות. דוגמה לכך היא אלגוריתם דייקסטרה המשמש למציאת מסלול מינימלי בגרף ממושקל: אם בגרף יש n קודקודים ו-m קשתות, יש לשמור בערימה n איברים שייצגו את הקודקודים, ולבצע עליהם m פעולות הקטנת הערך ו-n פעולות מחיקה. משום כך זמן הריצה בערימה בינארית יהיה $O(m\log n)$ אך מאחר ש-m>n, היינו מעדיפים לחסוך בזמן העלות של פעולת הקטנת הערך.

ערימת פיבונאצ'י משמשת למטרה זאת. היא גמישה יותר והמבנה בה פחות קבוע ובשל כך פעולה בודדת יכולה לקחת יותר זמן מבערימה בינומית רגילה, אך יתרונה הוא בכך שהעלות לשיעורין שלה, כלומר זמן הריצה של סדרת פעולות - קטן יותר. כך לדוגמה זמן הריצה של n פעולות "הקטנת הערך", שכל אחת מהן לוקחת $O(n)$ במקרה הגרוע, לוקח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} בלבד לכולן (בממוצע, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} לכל פעולה). וכך זמן הריצה של אלגוריתם דייקסטרה יורד ל- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(m+n\log n)} .

מימוש

קובץ:Fibonacci heap.png

ערימת פיבונאצ'י

ערימת פיבונאצ'י ממומשת, בדומה לערימה בינומית, אוסף עצים. כל אחד מהעצים מקיים את "כלל הערימה" - ערך כל קודקוד לא גדול מערכי בניו. את השורשים של העצים מחזיקים ברשימה מקושרת דו כיוונית (כלומר עם מצביעים קדימה ואחורה) בנוסף שומרים מצביע לאיבר המינימלי, כדי לאפשר את החזרתו ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} .

על העצים יש מספר הגבלות שמבטיחות זמן ריצה מהיר: דרגת כל קודקוד (כלומר מספר ילדיו) היא לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log n)} , וגודל תת-עץ שדרגת השורש שלו היא k הוא לפחות כערך המספר ה-k+2 בסדרת פיבונאצ'י (ומכאן השם). כדי לשמור על כללים אלה, דואגים שאם "כורתים" שני תתי-עצים (כלומר הופכים את השורשים שלהם לעצים חדשים בערימה) כורתים גם את אביהם (אלא אם כן הוא שורש) בעזרת סימון קודקודים. שיטה זאת מבטיחה חסם תחתון על גודל העצים, אולם היא מביאה למספר גדול של עצים; כדי לתקן זאת, בפעולה "מחיקת מינימום" (שתתואר להלן) דואגים לאחד חלק מהעצים.

פעולות

שגיאה ביצירת תמונה ממוזערת:

אותה הערימה מיד אחרי מחיקת המינימום, לפני התיקון.

קובץ:Fibonacci heap extractmin2.png

אותה הערימה אחרי תיקון העץ.

שגיאה ביצירת תמונה ממוזערת:

הערימה העליונה לאחר הקטנת הערך של 9 ל-0. שלושה עצים חדשים נוספו.

• הכנסה, מיזוג: בפעולות אלו בא לידי ביטוי המימוש ה"עצלני" של הערימה: הן ממומשות במהירות, במחיר של צעדים נוספים שידרשו לעשות פעולות אחרות. בפעולת ההכנסה פשוט מוסיפים את האיבר בהתחלה, ובפעולת המיזוג משרשרים את הערימות ליצירת ערימה שמורכבת משתיהן. פעולות אלו לוקחות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} .
• מחיקת מינימום: בפעולה זאת ראשית יש למחוק את האיבר המינימלי ולהפוך את ילדיו לעצים חדשים, אותם יש למזג עם הערימה. אולם, כעת יש למצוא את המינימום החדש, פעולה העלולה לקחת בזמן הגרוע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} . משום כך מוסיפים בפעולה זאת גם את "תיקון הערימה": מאחדים עצים בעלי דרגה זהה לעץ חדש, על ידי הוספת השורש בעל הערך הגדול יותר כבן נוסף לשורש הקטן יותר. ממשיכים בפעולה זאת עד שלא נותרים עוד שני שורשים מאותה דרגה (כדי לעשות זאת באופן יעיל, מחזיקים מערך עם מצביעים לשורשים מהדרגות השונות, ולאחר מכן עוברים על השורשים האחרים ומאחדים אותם עם הדרגה המתאימה כפי שתואר לעיל). בסופו של דבר יש למצוא את המינימום החדש - ואת זאת עושים על ידי ריצה על השורשים, ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log n)} (מאחר שיש לכל היותר עץ אחד מכל דרגה, והדרגות גדלות באופן מעריכי כמו סדרת פיבונאצ'י).
• הקטנת ערך: בפעולה זאת מקטינים תחילה את הערך. אם הוא היה שורש, יש לבדוק האם מצביע המינימום עדיין נכון ואם לא - לתקן. אם לא, יש לבדוק האם אביו עדיין קטן ממנו או שווה לו. אם לא, "כורתים" את תת-העץ שזהו השורש שלו, כלומר הופכים אותו לעץ חדש בערימה. לאחר מכן, מסמנים את אביו (אלא אם כן הוא שורש). אם אביו כבר מסומן, גם הוא נכרת והופך לעץ חדש, ומסמנים גם את אביו. ממשיכים כך עד שמסמנים קודקוד שלא היה מסומן, או מגיעים לשורש.
• מחיקה: את המחיקה ניתן לבצע על ידי הקטנת הערך ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -\infty} (כלומר קטן יותר מכל הערכים) ולאחר מכן מחיקת המינימום.

ניתוח

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

העלות הגרועה ביותר של פעולת מחיקת המינימום היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} . נחשב את העלות לשיעורין: בפעולה היקרה ביותר, שהיא איחוד העצים, על כל איחוד עצים אנחנו מקטינים באחד את הפוטנציאל, ועל כן העלות בסופו של דבר היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log n)} (הנובע מחיפוש העצים המתאימים). עדכון המינימום גם הוא ב-$O(\log n)$ ועל כן מקבלים שהעלות לשיעורין היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log n)} .

העלות הגרועה ביותר של פעולת הקטנת הערך היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} . נחשב את העלות לשיעורין: נניח והיו k קודקודים שנכרתו ברצף, כלומר כולם (למעט אולי הראשון) היו מסומנים ועכשיו כבר לא, ובנוסף האבא של האחרון אולי סומן, לכן מספר המסומנים קטן במספר שבין k ל-k-2. לעומת זאת, מספר העצים גדל ב-k ולכן הפוטנציאל ירד ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2(k-2)-k=k-4} . בוצעו k פעולות. סה"כ הזמן לשיעורין הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-(k-4)=4} כלומר קבוע. לכן זמן הריצה לשיעורין הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} .

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

ערימת פיבונאצ'י28668940Q1410737