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

ניתן להגדיר ערימת מקסימום טרנרית כעץ טרנרי (לכל קדקוד 3 בנים) ולהכליל את ה `heapify` שנלמד ל `heapify3` בהתאם. א) ניתן לשכן ערימה טרנרית במערך. איך נעבור מהורה לשלושת בניו? איך מקדקוד לאביו? ב) אחרי מחיקת האיבר המירבי משורש הערימה, (i) כמה קריאות ל `heapify3` נדרשות? (ii) כמה השוואות צריך בכל רמה? ג) מה המסקנה יחסית לשימוש בערימה בינרית?

רמז: השוו בין הערימה הבינרית והטרנרית על ידי בחינת שני גורמים: גובה העץ ומספר ההשוואות הנדרש בכל הפעלת `heapify`.

פתרון: א) כדי לשכן **ערימה טרנרית** במערך, נשתמש בדרך כלל ב**אינדקס מבוסס 0**. היחסים בין הורה לבניו הם כדלקמן: * **מהורה לבנים**: עבור קדקוד (הורה) הנמצא באינדקס `i`, שלושת בניו יימצאו באינדקסים: `3i + 1` (בן שמאלי), `3i + 2` (בן אמצעי), ו-`3i + 3` (בן ימני). * **מבן לאב**: עבור קדקוד (בן) הנמצא באינדקס `j` (כאשר `j > 0`), אביו יימצא באינדקס `floor((j-1)/3)`. לדוגמה, אביו של הקדקוד באינדקס `j=10` הוא `floor((10-1)/3) = floor(3) = 3`. בניו של הקדקוד באינדקס `i=3` הם `3*3+1=10`, `3*3+2=11`, ו-`3*3+3=12`. ב) לאחר מחיקת האיבר המרבי מהשורש, מחליפים אותו עם האיבר האחרון בערימה ומפעילים את הפעולה `heapify3` על השורש כדי לתקן את **תכונת הערימה**. (i) במקרה הגרוע, האיבר החדש בשורש יצטרך "לשקוע" עד לעלה. מסלול זה הוא באורך גובה העץ. לכן, מספר הקריאות הרקורסיביות ל-`heapify3` שיידרש הוא כגובה העץ, שהוא `O(log_3 n)` עבור ערימה עם `n` איברים. (ii) בכל קריאה ל-`heapify3` על קדקוד מסוים, עלינו למצוא את האיבר הגדול ביותר מבין הקדקוד עצמו ושלושת בניו (כלומר, מתוך 4 איברים). מציאת המקסימום בקבוצה של 4 איברים דורשת **3 השוואות**. ג) כדי להשוות את יעילות הערימה הטרנרית ל**ערימה בינארית**, ננתח את מספר ההשוואות הכולל הנדרש בפעולת `delete-max` (שנשלטת על ידי `heapify` כלפי מטה). * **בערימה בינארית**: גובה העץ הוא כ-`log_2 n`. בכל רמה נדרשות 2 השוואות (כדי למצוא מקסימום מבין 3 איברים). סה"כ השוואות במקרה הגרוע: `2 * log_2 n`. * **בערימה טרנרית**: גובה העץ הוא כ-`log_3 n`. בכל רמה נדרשות 3 השוואות. סה"כ השוואות במקרה הגרוע: `3 * log_3 n`. נשווה את שני הביטויים. נמיר את הלוגריתם הטרנרי לבסיס 2 באמצעות נוסחת המעבר בין בסיסים: `log_3 n = log_2 n / log_2 3`. מספר ההשוואות בערימה טרנרית הוא: `3 * (log_2 n / log_2 3) = (3 / log_2 3) * log_2 n` כעת נשווה את המקדמים: `2` (בערימה בינרית) ו-`3 / log_2 3` (בערימה טרנרית). ידוע כי `log_2 3 ≈ 1.585`. לכן, המקדם של הערימה הטרנרית הוא `3 / 1.585 ≈ 1.89`. מאחר ש-`1.89 < 2`, נובע כי `(3 / log_2 3) * log_2 n < 2 * log_2 n`. **מסקנה**: למרות שערימה טרנרית דורשת יותר השוואות בכל רמה בתהליך `heapify` כלפי מטה (3 לעומת 2), **הגובה הנמוך יותר של העץ** (`log_3 n` לעומת `log_2 n`) מפצה על כך, והתוצאה הסופית היא **פחות השוואות בסך הכל** עבור פעולת מחיקת המקסימוм. גם פעולת **הכנסה** תהיה מהירה יותר בערימה טרנרית, שכן היא דורשת השוואה אחת בלבד בכל רמה, ומספר הרמות קטן יותר. לכן, ערימה טרנרית יעילה יותר מערימה בינארית במונחים של מספר ההשוואות. $\blacksquare$