מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/מיזוג 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)$.

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

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

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

# 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