בזמנו שעשיתי מבני נתונים הפציצו אותי בשאלות תיאורטיות על ערימת פיבונצ'י - זה לא הוגן .

אם אתה ברוח של מבנ"ת אז קח שאלה נחמדה:
נתון מערך עם n איברים. צריך לקבוע האם איבר מופיע במערך יותר מ-n/lg n פעמים.
(הערה: אפשר לעשות את זה מהר יותר מ-nlg n)

בהצלחה במבני נתונים, במקרה הכי גרוע באמת יש מועד ב'

באשר לפתרון - זה כיוון טוב, אבל יש גישה נוחה יותר לדעתי. בוא נצא מנקודת הנחה שאם איבר מופיע n/lg n פעמים אז הוא אחד מהאיברי המערך שדרגתם i * n/lg n כאשר i רץ בין 1 ל-lg n. כאמור אם נעשה lg n קריאות ל-Select מתאים, זה יעלה nlg n כמו שאמרת. במקום, אפשר להסתכל על 2lg n חציוני המערך וכל פעם שאנחנו מוצאים חציון, לחלק אותו לשני תתי מערכים ועל כל אחד מהם למצוא חציון.
כלומר כל איטרציה תמצא חציון למערך, תחלק את המערך הנתון לשני תתי מערכים ותקרא רקורסיבית לפונקציה על כל אחד משני תתי המערכים שהתקבלו.
באופן זה אתה יכול למצוא את lg n (או 2lg n) חציוני החציונים בעלות של nlg lg n.

בכל מקרה, כמו שאמרתי וגם אתה - זה אכן מלווה בד"כ בשינון של הרבה הוכחות, קח את הזמן.

בכל אופן, בנוגע לחידה:
כמו שאמרתי, אם איבר מופיע n/lg n פעמים אז הוא חייב להיות מדרגה (סדר סטטיסטי) של k * n/lg n (כמו שאם למשל אני רוצה לדעת האם קיים איבר המופיע n/5 פעמים במערך אז אני אקרא ל-Select עם n/5, 2n/5 , ... , 4n/5 , n - אחת מהתוצאות חייבת להיות האיבר הזה).
יש לי סה"כ lg n כאלו, ואם אני סתם אקרא ל-Select אז זה יעלה לי nlg n שזה לא טוב.

במקום נמצא את log n החציונים באופן יעיל:
נחלק את המערך לשני מערכים ונמצא לכל תת מערך את החציון שלו (כלומר נמצא את החציון וניצור 2 תתי מערכים, באחד כל האיברים הקטנים ממנו, באחר כל האיברים הקטנים ממנו).
כל איטרציה על מערך בגודל n לוקחת 2n (כאמור n עבור מציאת החציון ו-n עבור חלוקת המערך לשני תתי מערכים).
עומק הרקורסיה הוא log log n.
בסה"כ נקבל שכל רמה בעץ הרקורסיה עלותה היא 2n.
כלומר עלות החישוב הינה 2nlog log n.

בגלל שאתה עובד בצורה מאוזנת, אתה מחשב lg n חציונים ב-nlg lg n במקום ב-nlg n.

לבסוף אתה מחזיק ביד lg n ערכים כאשר אתה יודע שאם קיים איבר במערך המופיע n/lg n פעמים הוא בהכרח אחד מהערכים שאתה מחזיק. מפה לא קשה להמשיך.