שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2012 - ערימות

השאלה מתייחסת לעץ חיפוש בינארי (בינארי בדרגה בעל מקבילית $S$ בעץ אבותיו. תנועת רשימה. א) Build$(S,L)$ – בנייה הממנה $S$ מרשימה $L$ בזמן הקטעים $L$ בתוך $O(n)$. ב) Max$(S)$ – החזרת ערך קסטימלי בתוך $O(1)$. ג) Min$(S)$ – החזרת ערך מינימלי בתוך $O(1)$. ד) delete-max$(S)$ – מחיקת ערך קסטימלי בתוך $O(\log n)$. ה) delete-min$(S)$ – מחיקת ערך מינימלי בתוך $O(\log n)$. הסברו בקצרה כיצד תתבעו כל פעולה.

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

פתרון: ניתן לממש את מבנה הנתונים הנדרש באמצעות שילוב של **ערימת מינימום** ו**ערימת מקסימום**. שתי הערימות יכילו את אותה קבוצת איברים מהרשימה $L$. התכונה המרכזית היא שכל איבר בערימה אחת יחזיק **מצביע** לאיבר התואם לו בערימה השנייה. הצלבה זו מאפשרת לבצע מחיקות מסונכרנות ביעילות. א) **Build(S,L)** – בניית המבנה מרשימה $L$ בגודל $n$: 1. ניצור שני מערכים בגודל $n$, אחד עבור כל ערימה. עבור כל ערך $v_i$ ברשימה $L$, ניצור צומת מתאים בכל מערך. 2. נאכלס את המצביעים: כל צומת במערך הראשון יצביע על הצומת התואם לו במערך השני, ולהיפך. שלב זה לוקח $O(n)$. 3. נפעיל את אלגוריתם הבנייה הלינארי (Floyd's algorithm) כדי להפוך את המערך הראשון ל**ערימת מינימום** בזמן $O(n)$. 4. באופן דומה, נהפוך את המערך השני ל**ערימת מקסימום** בזמן $O(n)$. הסיבוכיות הכוללת של פעולת הבנייה היא $O(n) + O(n) + O(n) = O(n)$. ב) **Max(S)** – החזרת הערך המקסימלי: הערך המקסימלי במבנה הוא תמיד שורש **ערימת המקסימום**. ניתן לגשת אליו ולהחזירו בזמן קבוע, $O(1)$. ג) **Min(S)** – החזרת הערך המינימלי: הערך המינימלי במבנה הוא תמיד שורש **ערימת המינימום**. ניתן לגשת אליו ולהחזירו בזמן קבוע, $O(1)$. ד) **delete-max(S)** – מחיקת הערך המקסימלי: 1. נזהה את הערך המקסימלי, שנמצא בשורש ערימת המקסימום. נקרא לצומת זה $max\_root$. 2. באמצעות המצביע מ-$max\_root$, נמצא את הצומת התואם לו בערימת המינימום. נקרא לצומת זה $min\_twin$. 3. נבצע פעולת `extract-max` על ערימת המקסימום. פעולה זו מסירה את השורש ומארגנת מחדש את הערימה בזמן $O(\log n)$. 4. נמחק את הצומת $min\_twin$ מערימת המינימום. מכיוון שיש לנו מצביע ישיר לצומת, ניתן לבצע מחיקה של איבר כללי מערימה. הפעולה מתבצעת על ידי החלפת הצומת עם האיבר האחרון בערימה, הסרת האחרון, ולאחר מכן ביצוע `sift-up` או `sift-down` על האיבר שהועבר כדי לשמור על תכונת הערימה. פעולה זו לוקחת $O(\log n)$. הסיבוכיות הכוללת של מחיקת המקסימום היא $O(\log n) + O(\log n) = O(\log n)$. ה) **delete-min(S)** – מחיקת הערך המינימלי: התהליך סימטרי לחלוטין למחיקת המקסימום: 1. נזהה את הערך המינימלי בשורש ערימת המינימום, $min\_root$. 2. נשתמש במצביע כדי למצוא את הצומת התואם $max\_twin$ בערימת המקסימום. 3. נבצע `extract-min` על ערימת המינימום בזמן $O(\log n)$. 4. נמחק את $max\_twin$ מערימת המקסימום באמצעות המצביע הישיר בזמן $O(\log n)$. הסיבוכיות הכוללת של מחיקת המינימלי היא $O(\log n)$.