תוכן עניינים:
הגדרה - מה המשמעות של הייפ?
ערימה, בהקשר של מבנה נתונים, היא מבנה נתונים מבוסס עצים המספק את נכס הערימה, שבו לכל אלמנט מוקצה ערך מפתח, או שקלול. למפתח הערך הנמוך יש תמיד צומת אב עם מפתח בעל ערך גבוה יותר. זה נקרא מבנה ערימת מקסימום, ובין כל הצמתים, לצומת השורש יש את המפתח הגבוה ביותר.
לפעמים, למבנה מבוסס עץ יש כלל מבנה הפוך, כאשר לאלמנט עם מפתח ערך גבוה יותר יש תמיד מפתח ערך נמוך יותר כצומת אב. זה נקרא מבנה min-heap, ובין כל הצמתים, לצומת השורש יש את המפתח הנמוך ביותר.
Techopedia מסביר את Heap
אין מגבלות מעשיות על מספר הילדים שלכל צומת יכול להיות בערימה, למרות שלכל צומת יש בדרך כלל שניים לכל היותר. הערימה נחשבת ליישום היעיל ביותר של סוג נתונים מופשט, המכונה תור העדיפות. יישום ערימה חיוני באלגוריתמי גרף שונים (כולל האלגוריתם של דיקסטרה) וכן באלגוריתם המיון של ערימת המידות.
לערימות יש כמה שונות שונות שמשמשות ליישום תור עדיפות מסוג נתונים מופשטים ביעילות גבוהה. יישומים רבים, כמו אלגוריתמי גרף, דורשים הטמעה של תורים בעדיפות.
מערך הוא צורת היישום הנפוצה ביותר של ערימה, בה אין צורך להצביע על קישור כלשהו בין מרכיביה.
ערימות מבצעות פעולות מרובות, כולל:
- Find-max: מחפש את צומת המפתח הגבוהה ביותר בקבוצת צמתים
- Find-min: מחפש את צומת המפתח הנמוך ביותר מבין קבוצת צמתים
- מחק מקסימום: מוחק את צומת המפתח הגבוהה ביותר בקבוצת צמתים
- מחק דקות: מוחק את צומת המפתחות הנמוכה ביותר בקבוצת צמתים
ערימות כוללות גם פונקציות המבצעות מיזוג, הכנסה ושינוי מפתחות.
הגדרה זו נכתבה בהקשר של מבנה נתונים