א. נתון עץ ערכי מיקום, כאשר כל צומת מתואר על ידי הזוג (מפתח, גודל):

• שורש: (26, 20)
• ילדיו של (26, 20): שמאל (17, 12), ימין (41, 7)
• ילדיו של (17, 12): שמאל (7, 7), ימין (21, 4)
• ילדיו של (41, 7): שמאל (30, 5), ימין (47, 1)
• ילדיו של (7, 7): שמאל (3, 1), ימין (10, 2)
• ילדיו של (21, 4): שמאל (19, 1), ימין (21, 1)
• ילדיו של (30, 5): שמאל (28, 1), ימין (38, 2)
• ילדיו של (10, 2): ימין (12, 1)
• ילדיו של (38, 2): שמאל (35, 1), ימין (39, 1)
  (הערה: ייתכנו אי-דיוקים בתכונת הגודל של צמתים מסוימים. הניתוח יתבסס על הנתונים כפי שהם.)

1. הריצו את האלגוריתם למציאת האיבר במיקום ה-18 (כלומר OS_Select(root, 18)). פרטו את השלבים.
2. הריצו את האלגוריתם למציאת הדירוג של האיבר עם מפתח 35 (כלומר OS_Rank(T, x) כאשר x הוא מצביע לצומת עם מפתח 35). פרטו את השלבים.

ב.

1. נתון המערך הבא: A=[27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0]. במסגרת הפיכת המערך לערימה, מריצים את הפעולה heapify(A,3). הסבירו מדוע יש צורך בפעולה זו במסגרת בניית ערימה, והריצו את הפעולה. פרטו את השלבים. (הניחו אינדקסים מ-1 ושהכוונה היא לערימת מקסימום).
2. תארו אלגוריתם לבניית ערימה חוקית בגודל \(n\) שזמן ריצתו יהיה \(\Omega(n \log n)\). (הערה: בניית ערימה סטנדרטית באמצעות Build-Heap פועלת בזמן \(O(n)\). יש לחשוב על דרך חלופית).