שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2013 - מיון

נתון משדר 4 מוגדר כ- $A$ בגרישות לדרך של פרמטרים $k$. בצורתונו לזידרה עם דרך בינו המאחדים את אינדקסי $A$ ממחדד בך ש - $n/k$ הוא מידה כללית מדוקדק, $n/k$ הם הקצרובים הממתנים ינו הן קצרובים מדוקדק. ובכן עם שו - $n/k$ הם הקצרובים הממתנים לכינו המחדדים הממחיקים המוגדרים הממתנים. הרח"אח. הרח. אידך לדעות זרך $O(n \log k)$.

רמז: ניתן לראות את הבעיה כמיזוג של $k$ תת-מערכים ממוינים. השתמשו בתור עדיפויות (ערימת מינימום) כדי למצוא ביעילות את האיבר הקטן ביותר מבין כל ראשי תת-המערכים בכל שלב.

פתרון: השאלה, כפי שניתן להסיק מהנתונים והסיבוכיות הנדרשת, עוסקת במיון מערך $A$ בגודל $n$ אשר מורכב משרשור של $k$ תת-מערכים, כאשר כל תת-מערך ממוין וגודלו $n/k$. המטרה היא למיין את המערך כולו בסיבוכיות זמן של $O(n \log k)$. בעיה זו היא למעשה בעיית **מיזוג של $k$ רשימות ממוינות**. כדי לפתור אותה ביעילות, נשתמש ב**תור עדיפויות** (Priority Queue) הממומש באמצעות **ערימת מינימום** (Min-Heap). הערימה תסייע לנו למצוא בכל שלב את האיבר הקטן ביותר מבין כל האיברים הזמינים מכל תת-המערכים. **תיאור האלגוריתם:** 1. ניצור מערך פלט `B` בגודל $n$. 2. ניצור ערימת מינימום `H`. הערימה תחזיק זוגות (tuples) מהצורה `(value, list_index)`, כאשר `value` הוא ערך האיבר ו-`list_index` הוא האינדקס של תת-המערך שממנו הגיע האיבר (מ-0 עד $k-1$). 3. נאתחל את הערימה: עבור כל אחד מ-$k$ תת-המערכים, נכניס לערימה את האיבר הראשון שלו יחד עם אינדקס תת-המערך. כלומר, עבור $i = 0, \dots, k-1$, נכניס לערימה את הזוג `(A[i*(n/k)], i)`. בנוסף, נשמור מערך עזר `pointers` בגודל $k$ שיצביע לאינדקס הבא שיש לקרוא מכל תת-מערך (מאותחל ל-1 עבור כולם). 4. נבצע $n$ איטרציות, ובכל איטרציה נבצע את הפעולות הבאות: א. נשלוף מהערימה `H` את הזוג בעל הערך הקטן ביותר. פעולה זו נקראת `extract-min`. נסמן את הזוג ששלפנו ב-`(v, i)`. ב. נוסיף את הערך `v` למערך הפלט `B`. ג. ניגש לתת-המערך שממנו הגיע האיבר (אינדקס `i`). אם תת-המערך טרם הסתיים (כלומר, האינדקס ששמור ב-`pointers[i]` עדיין בתחום של תת-המערך), נכניס לערימה את האיבר הבא מאותו תת-מערך. כלומר, את הזוג `(value, i)` כאשר `value` הוא האיבר הבא, ונקדם את `pointers[i]` ב-1. לאחר $n$ איטרציות, הערימה תהיה ריקה ומערך הפלט `B` יכיל את כל איברי $A$ בסדר ממוין. **ניתוח סיבוכיות זמן:** - **אתחול הערימה (שלב 3):** אנו מכניסים $k$ איברים לערימה. כל פעולת הכנסה לערימה שגודלה עד $k$ לוקחת $O(\log k)$. לכן, שלב האתחול לוקח $O(k \log k)$. - **הלולאה הראשית (שלב 4):** הלולאה רצה $n$ פעמים, פעם אחת עבור כל איבר במערך הקלט. - בכל איטרציה, אנו מבצעים פעולת `extract-min` אחת ופעולת `insert` אחת (לכל היותר). - גודל הערימה נשאר $k$ (או פחות, לקראת הסוף) לאורך כל ריצת האלגוריתם, מכיוון שעל כל איבר שיוצא, נכנס איבר חדש (עד שאחד התת-מערכים נגמר). - לכן, כל איטרציה לוקחת $O(\log k) + O(\log k) = O(\log k)$. - **סה"כ סיבוכיות הלולאה:** $n \times O(\log k) = O(n \log k)$. **סיבוכיות הזמן הכוללת** של האלגוריתם היא הסכום של שלב האתחול והלולאה הראשית: $O(k \log k + n \log k)$. מאחר שבדרך כלל $k \le n$, הביטוי הדומיננטי הוא $O(n \log k)$, כנדרש בשאלה.$\blacksquare$