שיעור 13: Heaps ו-top-K

דמיינו חדר מיון בבית חולים: לא מטפלים לפי סדר הגעה, אלא בחולה הכי דחוף. מבנה שעושה בדיוק את זה נקרא 'ערימה' (heap) — תור עדיפויות שתמיד נותן גישה מהירה לקצה (הקטן או הגדול ביותר). ב-Python: heapq, עם הוספה/הוצאה ב-O(log n). זה הכלי הטבעי לבעיות 'top-K' — מציאת ה-K הגדולים או הקטנים ביותר.

ערימה היא כמו תור בבית חולים שתמיד שולף את החולה הדחוף ביותר הבא. ב-heapq של Python, ה'דחוף ביותר' הוא פשוט המספר הקטן ביותר.

ערימה (heap): מבנה נתונים (תור עדיפויות) שמאפשר push ו-pop ב-O(log n) ו-peek של האיבר הקצה (מינימום/מקסימום) ב-O(1).
ערימת מינימום: ערימה שבה האיבר הקטן ביותר נמצא תמיד בשורש; heapq של Python הוא ערימת מינימום ו-heappop מחזיר את המינימום.
top-K: למצוא את K האיברים הגדולים (או הקטנים) ביותר. אפשר לעשות זאת ב-O(n log K) בעזרת ערימה בגודל K, מהר יותר ממיון מלא.