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

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

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

פתרון: נשתמש במבנה נתונים המורכב משני מבנים אחרים: **ערימת מינימום** ($H_{min}$) ו**ערימת מקסימום** ($H_{max}$). שתי הערימות יכילו את כל האיברים מהרשימה $L$.\nכדי לאפשר מחיקה יעילה של איבר מערימה אחת כאשר הוא נמחק מהשנייה, כל איבר בערימה אחת יחזיק מצביע לאיבר התואם לו בערימה השנייה. כלומר, כל איבר (צומת) במבנה יהיה רשומה המכילה את הערך עצמו, ומצביע לצומת המקביל בערימה השנייה.\n\nלהלן פירוט הפעולות:\n\n**a. Build(S,L)**\nהבנייה תתבצע ב-$O(n)$ באופן הבא:\n1. ניצור שני מערכים, $A_{min}$ ו-$A_{max}$, בגודל $n$. כל תא במערכים יכיל רשומה (צומת) עם שדה לערך ושדה למצביע.\n2. נעבור על רשימת הקלט $L$. עבור כל איבר $v$ באינדקס $i$: ניצור שתי רשומות עבור הערך $v$. נמקם אחת ב-$A_{min}[i]$ והשנייה ב-$A_{max}[i]$.\n3. נאתחל את המצביעים: עבור כל $i$ מ-$0$ עד $n-1$, נגדיר שהמצביע ב-$A_{min}[i]$ יצביע לכתובת של $A_{max}[i]$, והמצביע ב-$A_{max}[i]$ יצביע לכתובת של $A_{min}[i]$. שלב זה לוקח $O(n)$.\n4. נהפוך את המערך $A_{min}$ לערימת מינימום ואת המערך $A_{max}$ לערימת מקסימום. פעולת ה-**Heapify** (בניית ערימה ממערך לא ממוין) מתבצעת בזמן $O(n)$. בכל פעם שמתבצעת החלפה (swap) בין שני איברים בערימה אחת במהלך בנייתה, נצטרך לעדכן את המצביעים ההדדיים באיברים המקבילים בערימה השנייה. פעולת החלפה כזו, הכוללת עדכון מצביעים, לוקחת $O(1)$. לכן, סיבוכיות ה-Heapify נשארת $O(n)$.\nהסיבוכיות הכוללת של הבנייה היא $O(n) + O(n) = O(n)$.\n\n**b. Max(S)**\nהערך המקסימלי נמצא תמיד בשורש של ערימת המקסימום, $H_{max}$. ניתן לגשת אליו בזמן $O(1)$.\n\n**c. Min(S)**\nהערך המינימלי נמצא תמיד בשורש של ערימת המינימום, $H_{min}$. ניתן לגשת אליו בזמן $O(1)$.\n\n**d. delete-max(S)**\n1. נמצא את האיבר המקסימלי בשורש של $H_{max}$.\n2. נשתמש במצביע שברשומת השורש של $H_{max}$ כדי למצוא את מיקום האיבר התואם ב-$H_{min}$ בזמן $O(1)$.\n3. נמחק את שורש $H_{max}$ (פעולת `delete-max` סטנדרטית). פעולה זו כוללת החלפה עם האיבר האחרון ותיקון הערימה כלפי מטה (sift-down), ומתבצעת ב-$O(\log n)$.\n4. נמחק את האיבר התואם מ-$H_{min}$. מכיוון שאנו יודעים את מיקומו, זוהי מחיקת איבר כלשהו מהערימה. פעולה זו מתבצעת גם היא על ידי החלפה עם האיבר האחרון ותיקון הערימה, ולוקחת $O(\log n)$.\nבכל החלפה המתבצעת בשתי הערימות, יש לעדכן את המצביעים ההדדיים כפי שהוסבר קודם (בזמן $O(1)$ להחלפה). הסיבוכיות הכוללת היא $O(\log n)$.\n\n**e. delete-min(S)**\nהתהליך סימטרי ל-`delete-max`:\n1. נמצא את האיבר המינימלי בשורש של $H_{min}$.\n2. נשתמש במצביע שבו כדי לאתר את האיבר התואם ב-$H_{max}$ ב-$O(1)$.\n3. נמחק את שורש $H_{min}$ ב-$O(\log n)$.\n4. נמחק את האיבר התואם מ-$H_{max}$ ב-$O(\log n)$.\nהסיבוכיות הכוללת היא $O(\log n)$.