ערימה - Heap

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

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