ערימה

במדעי המחשב ערימה (Heap) היא מבנה נתונים בצורת עץ מכוון שמקיים את "תכונת הערימה". תכונת הערימה אומרת שקיים יחס סדר בין ההורה לילדיו.

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

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


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

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

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

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

ערימה היא דרך לארגן נתונים בעץ. עץ כאן הוא מבנה עם צומת עליון ושכבות מתחתיו.

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

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


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

זו ערימה שעשויה מקבוצה של עצים מיוחדים. העיצוב הזה מאפשר לחבר שתי ערימות במהירות.

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

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