ערימה

ערך זה עוסק במבנה נתונים. אם התכוונתם לאזור הזיכרון הדינמי, ראו מקטעי זיכרון.

במדעי המחשב, ערימה (באנגלית: Heap) היא מבנה נתונים בצורת עץ מכוון המקיים תכונה בסיסית, הנקראת תכונת הערימה: המפתח של כל צומת בעץ קטן ממפתח אביו. כתוצאה מדרישה זו, הצומת בעל המפתח הגדול ביותר בכל הוא תמיד השורש של העץ, וניתן למצוא אותו בסיבוכיות זמן ‏$O(1)$, כלומר במספר פעולות קבוע, שאיננו תלוי במספר האיברים בערימה.

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

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

הערימות השונות הן המימושים היעילים ביותר של מבנה הנתונים המופשט תור עדיפויות.

סוגי ערימות

ערימה בינארית

דוגמה לערימה בינארית

ערימה בינארית היא ערימה שממומשת באמצעות עץ בינארי, כלומר לכל צומת לכל היותר שני בנים. בנוסף לתכונת הערימה, היא מקיימת תכונה נוספת הנוגעת לצורתה:

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

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

ערימה בינומית

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

• לכל דרגה נתונה זהה, קיים בערימה הבינומית לכל היותר עץ אחד שזוהי דרגת שורשו (כלומר, כל העצים בערימה הם מאורך שונה).

בשל תכונות אלו ערימה בינומית מסוגלת לאפשר מיזוג עם ערימה נוספת מסוגה בזמן מהיר.

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

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

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

ייצוג ערימה במערך סטטי

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

גודלו הלוגי של מערך יהיה n כמספר הקודקודים וישמר במשתנה נפרד heapSize.

1) מערך בו השורש במקום 0.

  * הילדים של קודקוד i באינדקסים 2i+1 (בן שמאלי), 2i+2 (בן ימני).
  * האבא של קודקוד i באינדקס [i-1/2].
  * העלים נמצאים באינדקסים: [n-1, n-2, n-3..., [n/2. 

2) מערך בו השורש במקום 1 (מתעלמים ממקום 0, שיטה זו מקלה על החישובים).

  * הילדים של קודקוד i באינדקסים 2i (בן שמאלי), 2i+1 (בן ימני).
  * האבא של קודקוד i באינדקס [i/2].
  * העלים נמצאים באינדקסים: [n, n-1, n-2..., [n/2.

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

ראו גם

• מיון ערימה

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

• "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF) (1987). Journal of the Association for Computing Machinery 34 (3): 596–615. doi:10.1145/28869.28874.