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

שאלה 1 1. (12 נקודות) נתון מערך בגודל $n$ המכיל ערימת מקסימום בגודל לא ידוע. כלומר, $x$ התאים הראשונים של המערך הם ערימה תקנית ושאר התאים מכילים את הערך אינסוף (וכאמור, $x$ אינו ידוע). עליכם לקבוע את ערכו של $x$ בזמן לוגריתמי ב־$x$. כלומר, אם $n = 2^{100}$ וגודל הערימה הסתבר להיות 30 אזי יש לבצע כ־5 פעולות ולא כ־100 פעולות. 2. (13 נקודות) נתונה ערימת מינימום שבה בכל רמה כל האיברים זהים. לדוגמה, הערימה $[1, 2, 2, 5, 5, 5, 5, 7, 7, 7, 7]$. כתבו שגרה בפסאדו־קוד המקבלת כקלט ערימה כנ״ל ואיבר נוסף $z$ ומחזירה אינדקס של מופע כלשהו של $z$ בערימה או $-1$ אם הוא לא קיים. זמן הריצה צריך להיות $O(\log \log n)$ כאשר $n$ הוא מספר האיברים בערימה.

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

פתרון: האלגוריתם מורכב משני שלבים, ומטרתו למצוא את גודל הערימה $x$ בסיבוכיות זמן $O(\log x)$. 1. **מציאת תחום חיפוש באמצעות הכפלה מעריכית (Exponential Search):** מכיוון ש-$x$ אינו ידוע, איננו יכולים לבצע חיפוש בינארי ישירות על כל המערך, שכן הדבר יוביל לסיבוכיות של $O(\log n)$. במקום זאת, נמצא תחילה תחום שבו $x$ חייב להימצא. נבדוק אינדקסים שהם חזקות של 2: $0, 1, 2, 4, 8, \dots, 2^k, \dots$. נמשיך להכפיל את האינדקס הנבדק כל עוד הערך באינדקס זה אינו אינסוף, וכל עוד לא חרגנו מגבולות המערך. נעצור באינדקס הראשון $i = 2^k$ שבו $A[i]$ הוא אינסוף (או ש-$i \ge n$). בשלב זה, אנו יודעים שהאינדקס האחרון של הערימה נמצא בתחום $[i/2, \min(i, n-1)]$. שלב זה לוקח $O(\log x)$ פעולות, מכיוון שאנו מגיעים לגודל מסדר גודל של $x$ תוך $\log_2 x$ הכפלות. 2. **חיפוש בינארי בתחום המצומצם:** כעת, לאחר שזיהינו תחום חיפוש שגודלו $O(x)$, נבצע **חיפוש בינארי** בתוך התחום הזה. מטרת החיפוש היא למצוא את האינדקס האחרון $j$ שעבורו $A[j]$ אינו אינסוף. האינדקס הבא, $j+1$, יהיה הראשון שיכיל אינסוף (או יהיה מחוץ לתחום הערימה). לכן, גודל הערימה הוא $x=j+1$. מכיוון שגודל התחום הוא $O(x)$, החיפוש הבינארי ייקח $O(\log x)$ זמן. הסיבוכיות הכוללת של האלגוריתם היא סכום זמני הריצה של שני השלבים: $O(\log x) + O(\log x) = O(\log x)$, כנדרש. $\blacksquare$