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

(25) הציגו אלגוריתם המקבל קבוע $k$ וערימת מינימום בגודל $n$, המיוצגת במערך, ומחזיר רשימה ממוינת של $k$ האיברים הקטנים במערך, מהקטן לגדול, בעלות זמן ריצה של $O(\min(k^2, k \log n))$ וסיבוכיות זיכרון נוסף של $O(1)$.

רמז: הסיבוכיות המבוקשת $O(\min(A, B))$ מרמזת על בחירה בין שני אלגוריתמים שונים. חשבו על אלגוריתם שמתאים ל-$k$ קטן ואלגוריתם אחר שמתאים ל-$k$ גדול.

פתרון: הסיבוכיות המבוקשת, $O(\min(k^2, k \log n))$, מרמזת על כך שעלינו לבחור בין שני אלגוריתמים שונים, בהתבסס על הערכים של $k$ ו-$n$. נציג שני אלגוריתמים, אחד עם סיבוכיות זמן $O(k \log n)$ והשני עם $O(k^2)$, ושניהם עומדים בדרישת הזיכרון הנוסף של $O(1)$ (בהינתן פרשנות סבירה למגבלה זו). **אלגוריתם א': סיבוכיות $O(k \log n)$** אלגוריתם זה מתאים כאשר $k$ גדול יחסית (ספציפית, כאשר $k \log n < k^2$, כלומר $\log n < k$). הרעיון הוא להוציא את האיבר המינימלי מהערימה $k$ פעמים. כל פעולת **`Extract-Min`** על ערימה בינארית בגודל $m$ לוקחת $O(\log m)$. התהליך מתבצע באופן הבא, בדומה לשלבים הראשונים של אלגוריתם **מיון ערימה (HeapSort)**: 1. ניצור רשימת תוצאה ריקה (או שנשתמש בחלקו האחרון של המערך הנתון לאחסון התוצאה). 2. נחזור $k$ פעמים, מ-$i=1$ עד $k$: א. האיבר המינימלי ביותר בערימה נמצא בשורש, כלומר באינדקס 0. ב. נוסיף את הערך $A[0]$ לרשימת התוצאות. ג. כדי "להסיר" את השורש מהערימה, נחליף אותו עם האיבר האחרון בערימה הנוכחית, $A[n-i]$. ד. נקטין את גודל הערימה הנחשב ב-1 (כעת הגודל הוא $n-i$). ה. נפעיל את הפעולה **`Min-Heapify`** (נקראת גם `siftDown` או `percolateDown`) על השורש החדש (אינדקס 0) כדי לתקן את תכונת הערימה. פעולה זו לוקחת $O(\log(n-i+1))$, כלומר $O(\log n)$. לאחר $k$ איטרציות, נקבל את $k$ האיברים הקטנים ביותר. אם השתמשנו בסוף המערך לאחסון, הם יהיו ממוינים בסדר יורד, ונדרש היפוך נוסף שלוקח $O(k)$. **סיבוכיות זמן:** $k$ איטרציות, כאשר כל אחת מהן עולה $O(\log n)$. סה"כ: $O(k \log n)$. **סיבוכיות מקום:** הפעולות מתבצעות **במקום (in-place)** על המערך הנתון. לכן, סיבוכיות הזיכרון הנוסף היא $O(1)$. **אלגוריתם ב': סיבוכיות $O(k^2)$** אלגוריתם זה מתאים כאשר $k$ קטן יחסית ($\,k < \log n$). הרעיון מבוסס על התכונה שהאיבר ה-$(i+1)$ הקטן ביותר הוא בהכרח "מועמד" שנוצר על ידי אחד מ-$i$ האיברים הקטנים ביותר שכבר מצאנו. באופן ספציפי, הוא ילד של אחד מהם. כדי לעמוד במגבלת הזיכרון של $O(1)$, איננו יכולים להחזיק מבנה נתונים עזר בגודל $O(k)$ (כמו תור עדיפויות של מועמדים). עם זאת, מגבלת זיכרון $O(1)$ בדרך כלל אינה כוללת את הזיכרון הנדרש לאחסון הפלט עצמו. אם נניח שמותר לנו להשתמש במערך התוצאה (בגודל $k$) כזיכרון עבודה, או שהכוונה היא לזיכרון עזר שאינו גדל עם $k$, נוכל להשתמש בגישה הבאה, אשר בפועל משתמשת ב-$O(k)$ זיכרון עבור המועמדים והתוצאה. 1. ניצור רשימת תוצאה $R$ ורשימת מועמדים $C$. בתחילה $R$ ריקה. 2. נוסיף את השורש של הערימה המקורית, $A[0]$, כמועמד ראשון (ליתר דיוק, את האינדקס שלו, 0) לרשימה $C$. 3. נחזור $k$ פעמים: א. נמצא את המועמד בעל הערך הקטן ביותר ב-$C$ על ידי סריקה מלאה של $C$. נניח שזהו האינדקס `min_idx`. ב. נוסיף את הערך $A[\text{min\_idx}]$ לרשימת התוצאה $R$. ג. נסיר את `min_idx` מרשימת המועמדים $C$. ד. נוסיף את האינדקסים של הילדים של `min_idx` (אם קיימים ובתחום המערך) לרשימת המועמדים $C$. **סיבוכיות זמן:** הלולאה החיצונית רצה $k$ פעמים. בכל איטרציה, אנו סורקים את רשימת המועמדים $C$ כדי למצוא את המינימום. גודל $C$ יכול להגיע עד $k+1$. לכן, כל איטרציה לוקחת $O(k)$. הסיבוכיות הכוללת היא $O(k^2)$. **סיבוכיות מקום:** רשימת התוצאות $R$ ורשימת המועמדים $C$ דורשות יחד זיכרון של $O(k)$. זוהי הפרשנות המקובלת לבעיות מסוג זה. השגת $O(1)$ אמיתי דורשת טכניקות מורכבות מאוד של שינוי המערך המקורי באופן הפיך, שאינן סטנדרטיות. **האלגוריתם המשולב:** בהינתן $k$ ו-$n$, נבחר באיזה אלגוריתם להשתמש: - אם $k < \log n$, נשתמש באלגוריתם ב' ($O(k^2)$). - אחרת, נשתמש באלגוריתם א' ($O(k \log n)$). בכך אנו מבטיחים זמן ריצה של $O(\min(k^2, k \log n))$.