מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגלים/מבנה נתונים לחציון דינאמי/שאלה

הגדרה: החציון של קבוצת מספרים $\displaystyle A$ מוגדר כך: נגדיר $\displaystyle A'='\{a_{1},...,a_{n}\}$ כסדרה ממוינת המורכבת מאיברי $\displaystyle A$; אם $\displaystyle n$ אי זוגי, החציון הוא האיבר האמצעי, ואם $\displaystyle n$זוגי, אז החציון הוא ממוצע שני האיברים האמצעיים.

דוגמה: החציון של $\displaystyle \{1,2,9\}$ הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים). החציון של $\displaystyle \{1,9,2\}$ הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים). החציון של $\displaystyle \{1,2,3,100\}$ הוא 2.5 (2 ו3 הם איבריה האמצעיים של איבריה הממויינים). החציון של $\displaystyle \{1,2,2,2,2,2,2,2,2,2,2,2,2,3,100\}$ הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים).

רוצים לממש ביעילות מבנה נתונים Median בעל הממשק הבא:

# Makes a Median data-structure.
Make-Median()

# Adds another value (v) to a Median data-structure (m).
Insert(m, v)

# Returns the median of all the values in
#	a Median data-structure (m).
Med(m)

להלן דוגמה לשימוש במבנה הנתונים:

# Makes a median data-structure.
m = Make-Median()

# Inserts 1.
Insert(m, 1)
# Inserts 9.
Insert(m, 9)
# Inserts 2.
Insert(m, 2)

# Prints 2 (the median of {1, 9, 2}).
Print( Med(m) )

# Inserts 100.
Insert(m, 100)

# Prints 4.5 (the median of {1, 9, 2, 100}).
Print( Med(m) )

אנא הסבר כיצד לממש את מבנה הנתונים ביעילות.