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

מבני נתונים ואלגוריתמים - מחברת קורס

מבנה נתונים לחציון דינאמי

שאלה

הגדרה:

החציון של קבוצת מספרים $\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) )

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

תשובה

להלן מימוש יעיל אפשרי:

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). ‏ הראשונה מיועדת לשמירת חצי האיברים הקטנים יותר, והיא ערימה בינרית השומרת על האיבר הגדול ביותר בראש הערימה; השנייה מיועדת לשמירת חצי האיברים הגדולים יותר, והיא ערימה בינרית השומרת על האיבר הקטן ביותר בראש הערימה.

אם הפרש הגדלים בין גדלי שתי הערימות הוא $\displaystyle \pm 1$ (כלומר, שתי הערימות מחלקות את כל האיברים לשני חלקים שווים כמעט בגדלם), אז החציון הוא בהכרח האיבר בראש אחת מהערימות, או ממוצע ראשי האיברים (שורות 1-5 של Med). זאת אומרת שמציאת החציון דורשת לכל היותר שתי קריאות לSize, Min,‏ וMax של ערימה בינרית - פעולות שהן $\displaystyle O(1)$ כל אחת.

כעת נשאר רק לדאוג שהפרש הגדלים בין שתי הערימות הוא אכן $\displaystyle \pm 1$ . כאשר מכניסים איבר חדש, בוחרים לאיזו ערימה להכניס אותו, על ידי השוואתו לחציון (שורות 1-4 של Insert). אם אחת הערימות נהיית גדולה מדי (לדוגמה max-bh), אז שולפים ממנה את איבר הראש, ודוחפים אותו לערימה השנייה.

העברה בין שני תורי הקדימויות בחציון דינאמי.

מבדיקת פעולות הערימה הבינרית שנעשות, קל להווכח שסיבוכיות Insert היא $\displaystyle O(\log(n))$ ,‏ וסיבוכיות Med היא $\displaystyle O(1)$ .‏

מיזוג k-ארי

שאלה

במיון מיזוג ראינו את הפונקציה Merge, המקבלת שני מערכים ממוינים ומחזירה מערך ממוין של איחוד איבריהם בסיבוכיות לינארית. בשאלה זו נרחיב זאת למיזוג $\displaystyle k$ מערכים ממוינים.

נניח שברשותנו מערך Values-Arrays = [Values_1, ..., Values_k] (שים לב שזהו מערך של מערכים). אנא כתוב פונקציה יעילה K-Merge(Values-Array) המקבלת את מערך $\displaystyle k$ המערכים הממוינים, ומחזירה מערך ממוין של איחוד איבריהם.

לכל $\displaystyle 1\leq i\leq k$ , נגדיר $\displaystyle n_{i}=$ Length(Values_i), ונניח ש $\displaystyle n_{i}\gg k$ ‏. אנא נתח תשובתך במונחי $\displaystyle n_{1},...,n_{k}$ ו $\displaystyle k$

תשובה

גרסה מפושטת

רעיון כללי ופסוודו-קוד

נפתור ראשית גרסה מפושטת מעט של הבעיה:

נניח שהקלט הוא מערך של רשימות מקושרות ממויינות (ולא מערך של מערכים ממויינים)
האלגוריתם שנכתוב ידפיס את הערכים הממוזגים (ולא יחזיר מערך של הערכים הממוזגים)

השינויים הללו אינם משנים מהותית את האלגוריתם. עיקר תרומתם בפישוט הפסוודו-קוד (מעט).

דוגמה:

נבנה תור קדימות שבו מקום ל $\displaystyle k$ איברים. תור קדימויות זה יכיל זוגות: האיבר הראשון בכל זוג מתאר ערך איבר שנלקח מרשימה כלשהי, והאיבר השני בכל זוג מתאר את מספר הרשימה ממנו הוא נלקח. קריטריון ההשוואה בין הזוגות הוא עפ"י איבריהן הראשונים (האיברים שנלקחו מהמהערכים).

נתחיל בכך שנכניס את האיבר הראשון מכ"א מהמערכים. להלן הפסוודו-קוד לכך:

# Takes an array of sorted linked lists (Values-Array)
# Returns a sorted array whose entries are the those of the union
#	of the arrays in Values-Array.
K-Merge(Values-Array)
1	k = Length(Values-Array)

	# Make a binary heap (that can hold up to k elements).
2	bh = Make-Binary-Heap()

3	for i in [1, ..., k]
4		p = ( Delete-Front( Value-Array[i] ), i)
5		Insert(bh, p)

...

דוגמה:

נניח שמדובר ברשימות המקושרות מהתרשים הקודם. לאחר הפעלת השורות הראשונות, כך ייראו הרשימות ותור הקדימויות:

כל אחת מהרשימות "איבדה" חוליה, ונוספו שלושה זוגות לתור הקדימויות: הזוג $\displaystyle 1.07,2$ מציין שהאיבר שנלקח מרשימה 2 הוא 1.07, הזוג $\displaystyle 1.08,1$ מציין שהאיבר שנלקח מרשימה 1 הוא 1.08, והזוג $\displaystyle 1.1,3$ מציין שהאיבר שנלקח מרשימה 3 הוא 1.1.

הזוג הקטן ביותר בתור הקדימויות כעת הוא $\displaystyle 1.07,2$ , מפני ש $\displaystyle 1.07<1.08<1.1$ , ורק האיבר הראשון של כל זוג רלוונטי לסדר מבחינת תור הקדימויות.

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

דוגמה:

באיטרציה הראשונה, הזוג הקטן ביותר הוא $\displaystyle 1.07,1$ . מדפיסים 1.07, ולוקחים את איבר הראש הבא מרשימה 1. כעת ייראו הרשימות והתור כך:

עכשיו תורכם:

מה יקרה באיטרציה השניה?

הפתרון

באיטרציה השניה הזוג הקטן ביותר הוא $\displaystyle 1.08,2$ . מדפיסים 1.08, ולוקחים את איבר הראש הבא מרשימה 2. כעת ייראו הרשימות והתור כך:

להלן הפסוודו-קוד המלא לגרסה זו:

# Takes an array of sorted linked lists (Values-Array)
# Returns a sorted array whose entries are the those of the union
#	of the arrays in Values-Array.
K-Merge(Values-Array)
1	k = Length(Values-Array)

	# Make a binary heap (that can hold up to k elements).
2	bh = Make-Binary-Heap()

3	for i in [1, ..., k]
4		p = ( Delete-Front( Value-Array[i] ), i)
5		Insert(bh, p)

6	while Size(bh) > 0
7		(v, i) = Delete-Min(bh)

8		Print(v)

9		if not Empty( Value-Array[i] )
10			p = ( Delete-Front( Value-Array[i] ), i )
11			Insert(bh, p)

נכונות

הוכחת הנכונות דומה מאד לזו של Merge (הממזגת שני מערכים). אפשר להוכיח (פורמאלית באינדוקציה), שהאיבר הקטן ביותר שטרם הודפס הוא אחד מ(לכל היותר) $\displaystyle k$ האיברים הראשונים בכל רשימה מקושרת. בנוסף, הוכחנו שהתור בוחר את האיבר הקטן ביותר, מה שאומר שבחרנו את האיבר הקטן ביותר בקבוצת האיברים המכילה בהכרח את האיבר הקטן ביותר.

ניתוח סיבוכיות

קל להווכח שהשורות המשפיעות על הסיבוכיות הן הלולאות המתפעלות את התור. נשים לב שכל איבר ברשימות המקושרות יכול להכנס ולצאת לתור בדיוק פעם אחת, ולכן יש $\displaystyle n_{1}+\cdots +n_{k}$ פעולות כאלה. נשים גם לב שהתור לעולם לא יכיל יותר מ $\displaystyle k$ איברים, ולכן כל פעולה כזו היא $\displaystyle O(\log(k))$ . הסיבוכיות, לכן, היא $\displaystyle O\left(\left(n_{1}+\cdots +n_{k}\right)\cdot \log(k)\right)$ .

עכשיו תורכם:

הראה שקיימים איברים כך שהסיבוכיות היא

\displaystyle \Omega \left(\left(n_{1}+\cdots +n_{k}\right)\cdot \log(k)\right)

, והסק מכאן שסיבוכיות המקרה הגרוע הנה

$\displaystyle \Theta \left(\left(n_{1}+\cdots +n_{k}\right)\cdot \log(k)\right)$ .

הגרסה לבעיה המקורית

בעזרת מספר שינויים, אפשר לפתור את הבעיה המקורית.

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

# Takes an array of sorted arrays (Values-Array)
# Returns a sorted array whose entries are the those of the union
#	of the arrays in Values-Array.
K-Merge(Values-Array)
1	k = Length(Values-Array)

	# Make a binary heap (that can hold up to k elements).
2	bh = Make-Binary-Heap()

3	total-size = 0

4	for i in [1, ..., k]
5		total-size = total-size + Length(Value-Array[i])

6		p = (Value-Array[i][1], i, 2)
7		Insert(bh, p)

8	Merged = Make-Array(total-size)

9	m = 1

10	while Size(bh) > 0
11		(v, i, j) = Delete-Min(bh)

12		Values[m++] = v

13		if j ≤ Length(Value-Arrays[i])
14			p = (Value-Array[i][j], i, j + 1)
15			Insert(bh, p)	

16	return Merged

Heapsort

שאלה

להלן אלגוריתם הידוע בשם Heapsort (מיון תור קדימות):

# Heap sort. 
# Takes an array (Values), and sorts it in increasing order.
Heapsort(Values)
1	bh = Array-To-Heap(Values)

2	for i in [1, ..., Length(Values)]
3		Values[i] = Delete-Min(bh)

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

להלן ווריאציה אחרת של האלגוריתם:

# Heap sort. 
# Takes an array (Values), and sorts it in increasing order.
Heapsort(Values)
1	bh = Make-Binary-Heap()

2	for i in [1, ..., Length(Values)]		
3		Insert(bh, Values[i])

4	for i in [1, ..., Length(Values)]		
5		Values[i] = Delete-Min(bh)

אנא חזור על שני הסעיפים הקודמים לגבי ווריאציה זו.

תשובה

גרסה עם Build-Heap

קל לראות שהאלגוריתם עובד: כפי שראינו בבניית ערימה בינרית ממערך, Build-Heap מייצרת ערימה תקינה ממערך, והרי Delete-Min מוציאה ומחזירה את האיבר הקטן ביותר.
הסיבוכיות היא $\displaystyle \Theta (n\cdot \log(n))$ במקרה הגרוע. ראינו מימוש לBuild-Heap שעובד בזמן $\displaystyle \Theta (n)$ ,‏ ואנו יודעים שסיבוכיות Delete-Min על ערימה בת $\displaystyle i$ איברים היא $\displaystyle \Theta (\log(i))$ במקרה הגרוע. סיבוכיות הלולאה 3-4, לכן, היא $\displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))$ (ראה גם טורים שימושיים בסדרי גדילה).

גרסה עם סדרת פעולות Insert

אין שינוי בנכונות, כי הלולאה 3-4 גם כן מייצרת ערימה תקינה מהמערך, ואין הבדל מנקודה זו.
אף הסיבוכיות אינה שונה, מפני שבמקום הביטוי $\displaystyle \Theta (n)+\Theta (n\cdot \log(n))$ (בסעיף הקודם), נקבל כעת $\displaystyle \Theta (n\cdot \log(n))+\Theta (n\cdot \log(n))$ . שני הביטויים שקולים (מבחינת סדרי הגדילה).

אופטימיזציית פעולה יחידה מממשק תור קדימויות

שאלה

באפליקציה מסויימת, יש צורך במבנה נתונים התומך בפעולות Insert(pq, v),‏ Delete-Min(pq),‏ וMin(pq).‏ משמעות פעולות אלו היא בדיוק זו של תור קדימויות - מדובר במבנה נתונים המשתמש באיזושהי השוואה כדי לספק את האיבר הקטן בכל עת.

ידוע שבאפליקציה זו, מספר הפעולות הצפוי מסוג Delete-Min(pq) וMin(pq) הוא זניח יחסית למספר הפעולות הצפוי מסוג Insert(pq, v).‏ אנא הצע מימוש כך שInsert(pq, v) יהיה יעיל ככל האפשר. מה סיבוכיות שתי הפעולות האחרות במימוש שהצעת?
האם ייתכן מימוש לתור קדימויות בו הן Insert(pq, v) והן Delete-Min(pq) יעבדו בזמן $\displaystyle O(1)$ ?

שימו לב:

#בסעיף הראשון, עליך למצוא יעיל ככל האפשר לInsert(pq, v). אין צורך למצוא מימוש יעיל במיוחד לשתי הפעולות האחרות.

אפשר לפתור את הסעיף השני גם מבלי לפתור את הסעיף הראשון.

תשובה

סעיף זה הוא טריביאלי. נשתמש ברשימה מקושרת דו-כוונית (ייתכנו מימושים אחרים, כמובן). Insert תקרא לInsert-Front של רשימה מקושרת, ותעבוד בזמן $\displaystyle O(1)$ . את Min וDelete-Min נממש בעזרת לולאות על חוליות הרשימה. סיבוכיות כל אחת מפעולות אלה תהיה לינארית במספר החוליות במקרה הגרוע.
נזכר שבהנתן תור קדימויות, ניתן לממש בעזרת סידרת $\displaystyle n$ פעולות Insert ולאחריה סידרת $\displaystyle n$ פעולות Delete-Min (באופן כמעט זהה לHeapsort). לו כל פעולה היתה עובדת בזמן $\displaystyle O(1)$ , אז ניתן היה למיין בזמן לינארי, בניגוד לחסם התחתון על מיון מבוסס-השוואות שלמדנו.

איחוד תורי קדימויות

שאלה

רוצים לממש את הפונקציה Union(bh_1, bh_2),‏ המקבלת שתי ערימות בינריות, ומחזירה ערימה בינרית שאיבריה הם איחוד איברי bh_1 וbh_2.

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

תשובה

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

מימושים חלופיים לבניית תור קדימויות ממערך

שאלה

הסטודנט העיראקי איפ חמיס תברא מתבונן בקטע הקוד הבא:

# Makes a binary heap from an array (Values).
Build-Heap(Values)
1	bh = Make-Priority-Queue()
	
2	bh.size = Length(Values)	
	
3	for i in [1, ..., Length(Values)]
4		bh.Values[i] = Values[i]
		
5	Arrange(bh)
	
6	return bh

קטע קוד זה מקבל מערך, ומחזיר ערימה בינרית . איפ חוכך בדעתו כיצד מומשה הפונקציה Arrange. (אנו למעשה כבר ראינו את המימוש הבא:

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Down(bh, i)

אך הוא אינו יודע זאת).

מספר אפשרויות עולות על דעתו:

Arrange(bh)
1	for i in [⌊Length(bh.Values) / 2⌋, ..., 1]
2		Bubble-Down(bh, i)

Arrange(bh)
1	Merge-Sort(bh.Values)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Down(bh, i)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Up(bh, i)

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Up(bh, i)

עבור כל אחת מהאפשרויות, אנא הוכח או הפרך את הטענה שבהכרח תתקבל ערימה תקנית, ונתח את הסיבוכיות במקרה הגרוע (בלי קשר לשאלה האם תתקבל ערימה תקנית).

תשובה

הטענה נכונה. נניח שבערימה יש $\displaystyle s$ איברים. האיבר האחרון בערימה הוא באינדקס $\displaystyle s$ , ואביו (אם יש לו) בהכרח יושב ב $\displaystyle \left\lfloor {\frac {s}{2}}\right\rfloor$ . לכן, למרות שהלולאה אינה עוברת על כל האיברים, היא מדלגת רק על ערימות בעלי איבר יחיד, שהן, עפ"י תכונת הערימה, תקינות. הלולאה תתקן כל ערימה שדורשת תיקון, בדיוק מהסיבה שראינו בהרצאה. הסיבוכיות היא $\displaystyle \Theta (n)$ . אפשר לראות שהלולאה עוברת על חצי מהאיברים, ולכן היא $\displaystyle \Omega (n)$ . מצד שני, היא עושה פחות מBuild-Heap, וזו היתה $\displaystyle O(n)$ , ולכן גם לולאה זו $\displaystyle O(n)$ .
הטענה נכונה. אם ילדו השמאלי של איבר במקום $\displaystyle i$ נמצא באינדקס $\displaystyle 2\cdot i$ , וילדו הימני נמצא באינדקס $\displaystyle 2\cdot i+1$ , אז כל מסלול מהשורש לעלה עובר על סדרת אינדקסים מונוטונית עולה. לכן, אם המערך ממויין, כל מסלול מהשורש לעלה יעבור על סדרת ערכים מונוטונית לא-יורדת. הסיבוכיות הנה מיון מיזוג, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$ .
הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [3,4,2,1]$ . הסיבוכיות הנה $\displaystyle \Theta (n)$ , בדיוק מהניתוח שכבר ראינו לגבי הפתרון מההרצאה.
הטענה נכונה. היות ש Bubble-Up(bh, i) אינו יכול להשפיע על איברים באינדקס מעל $\displaystyle i$ , הקוד שקול לסדרת פעולות Insert. מאותה סיבה, הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$ .
הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [4,1,2,3]$ . הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$ .