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

ברצוננו לבנות ערמת מקסימום $H$ בת $n$ איברים; לכל איבר $x$ בערמה נוסיף שדה $\min[x]$, המאחסן את הערך המינימלי בתת-ערמה המושרשת ב-$x$. הראו כיצד ניתן לשנות את השגרה BUILD-HEAP($H$), כך שבניית הערמה המכילה את השדות $\min[x]$ עדיין תתבצע בזמן לינארי.

רמז: בשגרת BUILD-HEAP הרגילה, אנו עוברים מהצמתים האחרונים לשורש ומבצעים HEAPIFY. חשבו כיצד ניתן לחשב את $\min[x]$ בזמן $O(1)$ לכל צומת תוך כדי התהליך.

פתרון: **הרעיון:** בשגרת BUILD-HEAP המקורית, עוברים על הצמתים מלמטה למעלה (מאינדקס $\lfloor n/2 \rfloor$ עד 1) ומבצעים MAX-HEAPIFY. **שינוי:** לאחר שמבצעים MAX-HEAPIFY לצומת $i$, נחשב את $\min[i]$ באופן הבא: ``` min[i] = key[i] if left[i] ≤ heap-size: min[i] = min(min[i], min[left[i]]) if right[i] ≤ heap-size: min[i] = min(min[i], min[right[i]]) ``` **חשוב:** צריך לחשב את $\min$ **אחרי** ה-HEAPIFY, כי HEAPIFY עשוי להחליף איברים. למעשה, עדיף לשלב את חישוב $\min$ בתוך HEAPIFY עצמו. בכל פעם שמבצעים החלפה ב-HEAPIFY ויורדים לבן, מעדכנים את $\min$ של האב. **אלטרנטיבה פשוטה יותר:** 1. מבצעים BUILD-HEAP רגיל – $O(n)$. 2. עוברים על כל הצמתים מלמטה למעלה (מהעלים לשורש), ולכל צומת $i$: $$\min[i] = \min(key[i], \min[left(i)], \min[right(i)])$$ (עם התייחסות מתאימה לעלים, שם $\min[i] = key[i]$.) שלב 2 לוקח $O(n)$ (פעולה אחת בזמן $O(1)$ לכל צומת). סה"כ: $O(n) + O(n) = O(n)$ – **זמן לינארי**.