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

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

רמז: בעת ביצוע HEAPIFY מלמטה למעלה, ניתן לעדכן את $\max[x]$ של כל צומת לפי ה-$\max$ של ילדיו. חשבו כיצד לשלב זאת בתוך BUILD-HEAP ללא תוספת זמן אסימפטוטית.

פתרון: **הרעיון:** בשגרת BUILD-HEAP, עוברים על הצמתים מלמטה למעלה (מ-$\lfloor n/2 \rfloor$ עד 1) ומבצעים HEAPIFY. נשנה את HEAPIFY כך שבנוסף לתיקון תכונת הערמה, גם יעדכן את $\max[x]$. **שינוי BUILD-HEAP:** 1. ראשית, לכל עלה $x$: $\max[x] \leftarrow \text{key}[x]$ (זמן $O(n)$ סה"כ). 2. בלולאה של BUILD-HEAP, עבור כל צומת $i$ מ-$\lfloor n/2 \rfloor$ עד 1: - בצע HEAPIFY($H$, $i$) כרגיל. - לאחר מכן, עדכן: $\max[i] = \max(\text{key}[i],\ \max[\text{left}(i)],\ \max[\text{right}(i)])$ (כאשר קיימים ילדים). למעשה, ניתן לשלב את עדכון ה-$\max$ בתוך HEAPIFY עצמו: בכל שלב של HEAPIFY, לאחר שהאלמנט "שוקע" למקומו, מעדכנים את $\max$ שלו. מכיוון שהעיבוד מתבצע מלמטה למעלה, כאשר מגיעים לצומת $i$, כל הצמתים בתת-העצים שלו כבר עודכנו, ולכן ערכי $\max$ של הילדים נכונים. **זמן ריצה:** בכל צומת, עדכון $\max$ לוקח $O(1)$ נוסף. סה"כ התוספת היא $O(n)$, ומכיוון ש-BUILD-HEAP המקורי רץ ב-$O(n)$, הזמן הכולל נותר $O(n)$.