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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
ערימה בינארית

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

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

מבנה[עריכת קוד מקור | עריכה]

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

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

פעולות[עריכת קוד מקור | עריכה]

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

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

ערימה d-ארית[עריכת קוד מקור | עריכה]

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

שימושים[עריכת קוד מקור | עריכה]

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