מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/מימושים חלופיים לArray-To-Heap/תשובה

1. הטענה נכונה. נניח שבערימה יש $\displaystyle s$ איברים. האיבר האחרון בערימה הוא באינדקס $\displaystyle s$, ואביו (אם יש לו) בהכרח יושב ב$\displaystyle \left\lfloor {\frac {s}{2}}\right\rfloor$. לכן, למרות שהלולאה אינה עוברת על כל האיברים, היא מדלגת רק על ערימות בעלי איבר יחיד, שהן, עפ"י תכונת הערימה, תקינות. הלולאה תתקן כל ערימה שדורשת תיקון, בדיוק מהסיבה שראינו בהרצאה. הסיבוכיות היא $\displaystyle \Theta (n)$. אפשר לראות שהלולאה עוברת על חצי מהאיברים, ולכן היא $\displaystyle \Omega (n)$. מצד שני, היא עושה פחות מBuild-Heap, וזו היתה $\displaystyle O(n)$, ולכן גם לולאה זו $\displaystyle O(n)$.
2. הטענה נכונה. אם ילדו השמאלי של איבר במקום $\displaystyle i$ נמצא באינדקס $\displaystyle 2\cdot i$, וילדו הימני נמצא באינדקס $\displaystyle 2\cdot i+1$, אז כל מסלול מהשורש לעלה עובר על סדרת אינדקסים מונוטונית עולה. לכן, אם המערך ממויין, כל מסלול מהשורש לעלה יעבור על סדרת ערכים מונוטונית לא-יורדת. הסיבוכיות הנה מיון מיזוג, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.
3. הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [3,4,2,1]$. הסיבוכיות הנה $\displaystyle \Theta (n)$, בדיוק מהניתוח שכבר ראינו לגבי הפתרון מההרצאה.
4. הטענה נכונה. היות ש Bubble-Up(bh, i) אינו יכול להשפיע על איברים באינדקס מעל $\displaystyle i$, הקוד שקול לסדרת פעולות Insert. מאותה סיבה, הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.
5. הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [4,1,2,3]$. הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.