ערימה

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

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

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

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

סוגי ערימות

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

ערך מורחב – ערימה בינארית

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

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

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

בזכות תכונה זו, דרך נוחה לייצג ערימה בינארית היא בתוך מערך, ובצורה קומפקטית בה אין צורך לשמור מצביעים מכל תא במערך לתאים המייצגים את בניו. בנו השמאלי של קודקוד יימצא באינדקס $2i+1$ ובנו הימני באינדקס $2i+2$.

באופן דומה אביו של קודקוד יימצא באינדקס $\lfloor (i-1)/2\rfloor$.

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

ערימה מסוג זה ניתנת לבניה ממערך לא ממוין בסיבוכיות $O(n)$ .

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

ערך מורחב – ערימה בינומית

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

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

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

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

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

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

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

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

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

גודלו הלוגי של מערך יהיה 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].
   • העלים נמצאים באינדקסים: 1+[n, n-1, n-2..., [n/2.

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

ראו גם

• מיון ערימה

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

מדיה וקבצים בנושא ערימה בוויקישיתוף

• ערימה, באתר MathWorld (באנגלית)

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