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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

הגדרה:

החציון של קבוצת מספרים מוגדר כך: נגדיר כסדרה ממוינת המורכבת מאיברי ; אם אי זוגי, החציון הוא האיבר האמצעי, ואם זוגי, אז החציון הוא ממוצע שני האיברים האמצעיים.




דוגמה:

  1. החציון של הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים).
  2. החציון של הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים).
  3. החציון של הוא 2.5 (2 ו3 הם איבריה האמצעיים של איבריה הממויינים).
  4. החציון של הוא 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) )

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