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