ערימות (heaps) - שאלות חזרה
1) איך נחזיק מבנה נתונים שיתמוך במציאת איבר
מינימלי וגם במקסימלי?
תשובה
תשובה: נחזיק שתי ערימות: אחת עם שורש כאיבר מקסימלי
והשנייה עם שורש כאיבר מינימלי.
הסתר תשובה
2) כיצד תשפר מבנה זה כך שיתמוך גם בהכנסת איבר
ומחיקת מינימלי ומקסימלי?
תשובה
תשובה: יש לזכור כי מחיקה רגילה בערימה היא פעולה
יקרה. ובערימה השניה האיבר הנמחק לא יהיה שורש. אבל מכיוון שבערימה
השניה יהיה האיבר בהכרח עלה, המחיקה תהיה פשוט החלפת האיבר הנמחק
בעלה האחרון, העלאת זה במידת הצורך, והוצאת העלה המבוקש. המבנה יהיה
אם כן: החזקת שתי ערמות, שבין איבריהן יהיה מצביע דו כיווני. בהכנסת
איבר הוא יוכנס לכל רשימה בנפרד, ולאחר מכן יתבצע הקישור, ובמחיקה
ימחק האיבר משתי הערימות, כמתואר.
הסתר תשובה
3) איך בכל זאת נוכל לבצע מחיקה בערימה?
תשובה
תשובה: בכל מקרה החיפוש של האיבר יעלה (O(N, לכן נוכל
ביעילות זאת פשוט להתייחס לערימה כמערך רגיל, למחוק בו איבר ב- (O(N,
ואז לבנות מחדש את הערימה, שוב ב- (O(N.
הסתר תשובה
