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

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

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

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

מבנה

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

עם זאת, בפועל אין צורך לממש עץ בינארי: די להחזיק את האיברים במערך, כשהאיברים מסודרים בו משמאל לימין, שורה אחרי שורה, כאשר ידוע שאביו של איבר הנמצא במקום ה-i הוא ${\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }$ ובניו נמצאים במקומות ה-${\displaystyle 2i+1,2i+2}$.

פעולות

עבור ערימת מינימום-

• הכנסה: כדי להכניס איבר חדש, מגדילים את גודל הערימה ב-1, מכניסים את האיבר החדש בסוף הערימה, ולאחר מכן, כל עוד הוא קטן מאביו, מחליפים אותו עם אביו. סיבוכיות ריצה: ${\displaystyle O(\log n)}$ (הסבר על סימון זה). עם זאת, על פי ניתוח לשיעורין הסיבוכיות של בניית ערימה בת ${\displaystyle n}$ איברים היא ${\displaystyle O(n)}$ בלבד.
• הוצאה: כדי להוציא איבר, מחליפים את האיבר המועד להוצאה באיבר האחרון במערך, מורידים את האיבר הנ"ל מסוף המערך, ומקטינים את גודל הערימה ב-1. לאחר מכן משווים בין האיבר שהוצאנו לבין איבר שהחלפנו ואם האיבר שהחלפנו קטן מהאיבר שהוצאנו אז כל עוד האיבר שהוחלף קטן מאביו, מחלפים אותו באביו, ואם האיבר שהוחלף גדול מאיבר שהוצא אז כל עוד האיבר שהוחלף גדול מבניו, מחליפים אותו בקטן שביניהם. סיבוכיות זמן ריצה: ${\displaystyle O(\log n)}$
• מציאת המינימום (הצצה): מחזירים את האיבר הראשון. סיבוכיות זמן ריצה: ${\displaystyle O(1)}$.
• מחיקת המינימום (שליפה): מוחקים את האיבר המינימלי, מעבירים את האיבר האחרון להתחלה, ולאחר מכן, כל עוד הוא לא קטן משני בניו, מחליפים אותו עם הקטן מביניהם. זמן ריצה: ${\displaystyle O(\log n)}$.
• הקטנת ערך: מקטינים ערך, ולאחר מכן, כל עוד הוא קטן מאביו, מחליפים אותו עם אביו. סיבוכיות זמן ריצה: ${\displaystyle O(\log n)}$.

בניגוד לערימה בינומית, ערימה בינארית לא תומכת במיזוג ערימות.

ערימה d-ארית

במקום לממש את הערימה כעץ בינארי, אפשר לממש אותה כעץ מכל דרגה אחרת. בערימה d-ארית לכל קודקוד d ילדים, ושאר המימוש בדומה. אביו של איבר הנמצא במקום ה-i הוא ${\displaystyle \left\lfloor {\frac {i-2}{d+1}}\right\rfloor }$ ובניו j נמצאים במקומות ה- ${\displaystyle d(i+1)+j+1}$. הכנסה והקטנת ערך יורדות ל-${\displaystyle O(\log _{d}n)}$, ואילו מחיקת המינימום עולה ל-${\displaystyle O(d\log _{d}n)}$ (משום שיש למצוא את הבן המינימלי).

שימושים

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

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

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

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

הערות שוליים

1. Thomas Porter; Istvan Simon (1974). "Random Insertion into a Priority Queue Structure" (PDF). Stanford University Reports. Stanford University. p. 13. נבדק ב-31 בינואר 2014. {{cite web}}: (עזרה)