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

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

ערימה בינארית
Min-heap.png
דוגמה לערימת מינימום בינארית
סיבוכיות מקום וזמן
ממוצע במקרה הגרוע
זיכרון:
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 הוא   ובניו נמצאים במקומות ה- .

פעולותעריכה

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

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

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

ערימה d-אריתעריכה

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

שימושיםעריכה

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

קישורים חיצונייםעריכה

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

הערות שולייםעריכה

  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}}: (עזרה)