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

תכננו מבנה נתונים $S$ שבאמצעותו ניתן לבצע את הפעולות הבאות בסיבוכיות זמן ריצה של $\Theta(1)$. אם מעדכנים מבנה נתונים שנלמד בקורס, יש לציין רק מה העדכונים שבצעתם במבנה. - $insert(S, x)$ - הכנסת איבר בעל המפתח $x$ ל-$S$; - $deleteLast(S)$: מחיקת האיבר שנכנס אחרון מהמבנה $S$; - $minKey(S)$: החזרת המפתח המינימלי של $S$; - $mult(S, d)$: הכפלת כל המפתחות במבנה במספר הממשי $d$;

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

פתרון: **מבנה הנתונים:** מחסנית כפולה עם מכפיל גלובלי. נשמור: 1. **מחסנית $Stack$** — כל תא מכיל זוג $(val, min)$ כאשר $val$ הוא הערך ה"מנורמל" של המפתח ו-$min$ הוא המינימום המנורמל מהתחתית ועד לתא הנוכחי. 2. **משתנה גלובלי $M$** — מכפיל מצטבר, מאותחל ל-$1$. המפתח האמיתי של איבר עם ערך מנורמל $val$ הוא $val \cdot M$. **insert(S, x):** הערך המנורמל הוא $v = x / M$. המינימום המנורמל החדש: $newMin = \min(v, Stack.top().min)$ (או $v$ אם המחסנית ריקה). דוחפים $(v, newMin)$ למחסנית. זמן: $\Theta(1)$. **deleteLast(S):** שולפים מראש המחסנית (pop). זמן: $\Theta(1)$. **minKey(S):** מחזירים $Stack.top().min \cdot M$. זמן: $\Theta(1)$. **mult(S, d):** מעדכנים $M = M \cdot d$. זמן: $\Theta(1)$. **הערה חשובה:** כאשר $d < 0$, המינימום עלול להשתנות (כי הכפלה במספר שלילי הופכת סדר). צריך לשמור גם מקסימום מנורמל בכל תא. אם $M > 0$ המינימום האמיתי הוא $min \cdot M$, ואם $M < 0$ המינימום האמיתי הוא $max \cdot M$. לכן כל תא במחסנית יכיל $(val, min, max)$ כאשר $min$ ו-$max$ הם המינימום והמקסימום המנורמלים. $minKey(S)$: אם $M > 0$ מחזירים $Stack.top().min \cdot M$, אחרת $Stack.top().max \cdot M$.