מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגלים/מבנה נתונים לחציון דינאמי/תשובה
להלן מימוש יעיל אפשרי:
Median
# A min binary heap.
# This will be used to store the half of the larger values.
1 min-bh
# A max binary heap.
# This will be used to store the half of the smaller values.
2 max-bh
# Makes a Median data-structure.
Make-Median()
1 m = Median()
2 m.min-bh = Make-Binary-Heap()
3 m.max-bh = Make-Binary-Heap()
# Adds another value (v) to a Median data-structure (m).
Insert(m, v)
1 if Size(m.max-bh) == 0 or v < Med(m)
2 Insert(m.max-bh)
3 else
4 Insert(m.min-bh)
5 if Size(m.max-bh) > Size(m.min-bh) + 1
6 Insert(m.min-bh, Delete-Max(m.max-bh))
7 else if Size(m.min-bh) > Size(m.max-bh) + 1
8 Insert(m.max-bh, Delete-Min(m.min-bh))
# Returns the median of all the values in a Median data-structure (m).
Med(m)
1 if Size(m.min-bh) == Size(m.max-bh)
2 return (Min(m.min-bh) + Max(m.max-bh)) / 2
3 if Size(m.min-bh) > Size(m.max-bh)
4 return Min(m.min-bh)
5 return Max(m.max-bh)
הנה הסבר לפתרון.
מבנה הנתונים כולל שני תורי קדימויות :max-bh וmin-bh (שורות 1-2 של Median ו2-3 של Make-Median). הראשונה מיועדת לשמירת חצי האיברים הקטנים יותר, והיא ערימה בינרית השומרת על האיבר הגדול ביותר בראש הערימה; השנייה מיועדת לשמירת חצי האיברים הגדולים יותר, והיא ערימה בינרית השומרת על האיבר הקטן ביותר בראש הערימה.
אם הפרש הגדלים בין גדלי שתי הערימות הוא (כלומר, שתי הערימות מחלקות את כל
האיברים לשני חלקים שווים כמעט בגדלם), אז החציון הוא בהכרח האיבר בראש אחת מהערימות, או ממוצע ראשי האיברים (שורות 1-5 של Med). זאת אומרת שמציאת החציון דורשת לכל היותר שתי קריאות לSize, Min, וMax של ערימה בינרית - פעולות שהן כל אחת.
כעת נשאר רק לדאוג שהפרש הגדלים בין שתי הערימות הוא אכן . כאשר מכניסים איבר חדש, בוחרים לאיזו ערימה להכניס אותו, על ידי השוואתו לחציון (שורות 1-4 של Insert). אם אחת הערימות נהיית גדולה מדי (לדוגמה max-bh), אז שולפים ממנה את איבר הראש, ודוחפים אותו לערימה השנייה.
מבדיקת פעולות הערימה הבינרית שנעשות, קל להווכח שסיבוכיות Insert היא , וסיבוכיות Med היא .
