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

רצונו להדוץ אט $m$ איברים הרדולעים בידיחור קבוצה של $n$ איברים המאופיינות בעיות אמרת. הראה/י אך לא קיים חסם תחתון של $\Omega(\log m) \neq O(\log n)$ 1.0 לכמה, בעירומת מסיסימון. הערה/י אז לזוגיא $O(m \log m)$. השמוש/מספר עיבודת עור.

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

פתרון: השאלה, על אף הניסוח המשובש, עוסקת ככל הנראה במציאת $m$ האיברים הקטנים ביותר מתוך קבוצה של $n$ איברים. נציג אלגוריתם יעיל לפתרון בעיה זו באמצעות **ערימת מקסימום** (Max-Heap). הרעיון המרכזי הוא לתחזק מבנה נתונים, במקרה זה ערימת מקסימום, בגודל $m$, אשר תכיל בכל רגע נתון את $m$ האיברים הקטנים ביותר שפגשנו עד כה במהלך סריקת המערך. האיבר בראש ערימת המקסימום הוא הגדול ביותר מבין $m$ האיברים הללו. כאשר אנו סורקים איבר חדש מהקלט, נשווה אותו לאיבר שבשורש הערימה. אם האיבר החדש קטן יותר מראש הערימה, הרי שהוא "ראוי" יותר להיכלל בקבוצת $m$ האיברים הקטנים ביותר, ולכן הוא יחליף את האיבר הגדול ביותר הנוכחי בקבוצה זו (זה שבשורש). **תיאור האלגוריתם:** 1. ניצור **ערימת מקסימום** ריקה $H$ בגודל $m$. 2. נבנה את הערימה $H$ מה-$m$ האיברים הראשונים של מערך הקלט. פעולה זו, הידועה כ-**Build-Heap**, מתבצעת בסיבוכיות זמן של $O(m)$. 3. כעת, נעבור על יתר $n-m$ האיברים במערך (החל מהאיבר באינדקס $m$). עבור כל איבר $x$: א. נשווה את $x$ עם האיבר הנמצא בשורש הערימה, $H_{root}$. ב. אם $x < H_{root}$: i. נחליף את ערך השורש בערך של $x$. ii. נבצע פעולת **Max-Heapify** על השורש כדי לשמר את תכונת ערימת המקסימום. פעולה זו מבטיחה שהאיבר הגדול ביותר "יצוף" בחזרה למעלה. סיבוכיות פעולה זו היא $O(\log m)$, כתלות בגובה הערימה. 4. לאחר סיום המעבר על כל $n$ איברי הקלט, הערימה $H$ מכילה את $m$ האיברים הקטנים ביותר מתוך הקבוצה כולה. **ניתוח סיבוכיות זמן:** - שלב 2, בניית הערימה הראשונית, לוקח $O(m)$ זמן. - שלב 3, המעבר על יתרת האיברים, כולל לולאה שרצה $n-m$ פעמים. בכל איטרציה, במקרה הגרוע ביותר (כאשר האיבר הנבדק קטן מראש הערימה), אנו מבצעים פעולת Heapify שעלותה $O(\log m)$. לכן, העלות הכוללת של שלב זה היא $O((n-m)\log m)$. - **סיבוכיות הזמן הכוללת** של האלגוריתם היא הסכום של שני השלבים: $O(m + (n-m)\log m)$. אלגוריתם זה יעיל במיוחד כאשר $m$ קטן משמעותית מ-$n$ ($m \ll n$), אז הסיבוכיות קרובה ל-$O(n \log m)$, שהוא שיפור ניכר על פני מיון מלא של המערך ב-$O(n \log n)$. בסיום פעולת האלגוריתם, האיברים בערימה אינם ממוינים. אם נדרש גם למיין אותם, ניתן להוציא את כולם מהערימה (תוך תיקון חוזר של הערימה), בעלות נוספת של $O(m \log m)$. $lacksquare$