- הגשות
- פתרונות
- פתרון רשמי
- תיאור
א. נתון המערך \([45,33,55,15,28,66,64,18,14,49]\).
הראו כיצד פועלת השגרה BUILD-MIN-HEAP על המערך הנתון.
ב. נתונה ערמת מקסימום A בת n איברים. מקטינים את כל איברי המסלול השמאלי בצורה הבאה:
\(A[2^i] \leftarrow A[2^i] - d\), לכל \(i = 0,1,...,\lfloor \log n \rfloor\), כאשר \(d > 0\).
- מהו הערך \(d\) המקסימלי שלא יוביל להפרת תכונת הערמה? הסבירו בצורה מפורטת ומדויקת.
- במקרה הכללי, תכונת הערמה מופרת אחרי הקטנת איברי המסלול השמאלי. כתבו שגרה לתיקון הערמה בזמן ריצה של \(O(\log^2 n)\).
בסעיף א', זכרו ש-BUILD-MIN-HEAP קוראת ל-MIN-HEAPIFY על כל צומת שאינו עלה, החל מהצומת האחרון שאינו עלה ועד לשורש. בסעיף ב', לאחר הקטנת ערך בצומת, תכונת ערימת המקסימום עלולה להיות מופרת רק בינו לבין ילדיו. שימו לב שניתן לתקן את הערימה על ידי קריאה ל-MAX-HEAPIFY על כל הצמתים שהשתנו, אך סדר הקריאות הוא קריטי.