שאלה 1
1. (12 נקודות) נתון מערך בגודל n המכיל ערימת מקסימום בגודל לא ידוע. כלומר, x התאים הראשונים של המערך הם ערימה תקנית ושאר התאים מכילים את הערך אינסוף (וכאמור, x אינו ידוע). עליכם לקבוע את ערכו של x בזמן לוגריתמי ב־x. כלומר, אם n=2100 וגודל הערימה הסתבר להיות 30 אזי יש לבצע כ־5 פעולות ולא כ־100 פעולות.
2. (13 נקודות) נתונה ערימת מינימום שבה בכל רמה כל האיברים זהים. לדוגמה, הערימה [1,2,2,5,5,5,5,7,7,7,7].
כתבו שגרה בפסאדו־קוד המקבלת כקלט ערימה כנ״ל ואיבר נוסף z ומחזירה אינדקס של מופע כלשהו של z בערימה או −1 אם הוא לא קיים. זמן הריצה צריך להיות O(loglogn) כאשר n הוא מספר האיברים בערימה.