הבדלים בין גרסאות בדף "ערימה בינארית"

נוספו 3,621 בתים ,  לפני 6 שנים
חדש
(חדש)
[[קובץ:Min-heap.png|שמאל|ממוזער|250px|ערימה בינארית]]
#הפניה [[ערימה#ערימה_בינארית]]
ב[[מדעי המחשב]], '''ערימה בינארית''' היא סוג של [[מבנה נתונים|מבנה הנתונים]] [[ערימה]]. יתרונה הגדול הוא בנוחות השימוש בה והמקום המועט הדרוש כדי לתחזק אותה.
 
הערימה משמשת בין השאר ל[[מיון (מדעי המחשב)|מיון]] המכונה [[מיון ערימה]], ולמימוש [[מבנה נתונים מופשט|מבנה הנתונים המופשט]] [[תור עדיפויות]].
 
==מבנה==
הערימה היא כ[[עץ בינארי]] מלא, כלומר שכל השורות, פרט אולי לאחרונה, מלאות, והאחרונה מלאה משמאל עד לנקודה מסוימת. בנוסף, היא מקיימת את "כלל הערימה": כל ערך של צומת אינו גדול משני בניו (ערימה זאת מכונה "ערימת מינימום"; אפשרי גם שכל צומת אינו קטן משני בניו, ואז היא נקראת "ערימת מקסימום").
 
עם זאת, בפועל אין צורך לממש עץ בינארי: די להחזיק את האיברים ב[[מערך (מבנה נתונים)|מערך]], כשהאיברים מסודרים בו משמאל לימין, שורה אחרי שורה, כאשר ידוע שאביו של איבר הנמצא במקום ה-i הוא <math>\lfloor \frac{i-1}{2} \rfloor</math> ובניו נמצאים במקומות ה-
<math>2i+1,2i+2</math>.
 
==פעולות==
* '''הכנסה''': כדי להכניס איבר חדש, מכניסים אותו בסוף הערימה, ולאחר מכן, כל עוד הוא קטן מאביו, מחליפים אותו עם אביו. זמן ריצה: <math>O(\log n)</math>. עם זאת, בניית ערימה בת n איברים לוקחת <math>O(n)</math> בלבד.
* '''מציאת המינימום''': מחזירים את האיבר הראשון. <math>O(1)</math>.
* '''מחיקת המינימום''': מוחקים את האיבר המינימלי, מעבירים את האיבר האחרון להתחלה, ולאחר מכן, כל עוד הוא לא קטן משני בניו, מחליפים אותו עם הקטן מביניהם. זמן ריצה: <math>O(\log n)</math>.
* '''הקטנת ערך''': מקטינים ערך, ולאחר מכן, כל עוד הוא קטן מאביו, מחליפים אותו עם אביו. זמן ריצה: <math>O(\log n)</math>.
בניגוד ל[[ערימה בינומית]], ערימה בינארית לא תומכת במיזוג ערימות.
 
==ערימה d-ארית==
במקום לממש את הערימה כעץ בינארי, אפשר לממש אותה כעץ מכל דרגה אחרת. בערימה d-ארית לכל קודקוד d ילדים, ושאר המימוש בדומה. אביו של איבר הנמצא במקום ה-i הוא <math>\lfloor \frac{i-1}{d} \rfloor</math> ובניו נמצאים במקומות ה-
<math>di+1,di+2,...,di+d</math>. הכנסה והקטנת ערך יורדות ל-<math>O(\log_d n)</math>, ואילו מחיקת המינימום עולה ל-<math>O(d\log_d n)</math> (משום שיש למצוא את הבן המינימלי).
 
==שימושים==
הערימה הבינארית משמשת ל[[מיון ערימה]]. במיון זה, בונים ערימה מהאיברים ולאחר מכן מוחקים אותם אחד אחד. יתרונו הוא שהוא לא דורש זכרון נוסף, וזמן הריצה שלו הוא הטוב ביותר האפשרי: <math>O(\log n)</math> במקרה הגרוע.
 
{{מבני נתונים}}
[[קטגוריה: ערימה|בינארית]]
8,258

עריכות