2.38. תורי עדיפויות

תור עדיפויות הוא מכל שתמיד יודע מי מבין הפריטים שלו הוא הקטן ביותר (או הגדול ביותר) מבלי למיין את כל המכל. heapq ממש כזה ב-MicroPython באמצעות list רגילה כאחסון ואלגוריתם מבוסס עץ שנקרא min-heap כדי לשמור את הפריט הקטן ביותר באינדקס 0.

2.38.1. המודל המנטלי

min-heap הוא רשימה המסודרת כך שהפריט בכל אינדקס קטן-או-שווה לפריטים שבאינדקסים 2*i + 1 ו-2*i + 2. סידור זה הופך שלוש פעולות לזולות:

• מציאת הפריט הקטן ביותר – הוא נמצא ב-heap[0]. חיפוש אינדקס בודד, ללא סריקה.

• הוספת פריט – הוא מבעבע כלפי מעלה דרך העץ, ומשווה מול הורה אחד בכל רמה. אלף פריטים הם בערך עשר השוואות; מיליון הם בערך עשרים.

• הסרת הפריט הקטן ביותר – אותו מסלול בכיוון הפוך, עם אותו מספר מצומצם של השוואות.

הרשימה אינה ממוינת. מעבר עליה מחזיר את הפריטים בסדר שרירותי. רק heap[0] מובטח להיות המינימום.

2.38.2. שלוש הפונקציות ב-MicroPython

heapq של MicroPython חושף בדיוק שלוש פונקציות:

• heapq.heappush() – מכניס פריט, תוך שמירה על אינוריאנט הערימה.

• heapq.heappop() – מסיר ומחזיר את הפריט הקטן ביותר.

• heapq.heapify() – מסדר מחדש רשימה קיימת לכדי ערימה במקום.

זהו כל המשטח. heappushpop, heapreplace, nlargest, nsmallest ו-merge של CPython אינם קיימים; הדפוסים שלהלן מראים כיצד לבנות את הנפוצים שבהם ביד.

התחלה מאפס:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

התחלה מנתונים קיימים:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

Heapify נוגע בכל פריט פעם אחת והוא מהיר באופן ניכר מדחיפת אותם פריטים אחד-אחד.

2.38.3. Top-N על זרם

שימוש טבעי בתור עדיפויות: מעקב אחר N הפריטים הגדולים ביותר בזרם שניתן לקרוא רק פעם אחת.

הטריק הוא לשמור min-heap בגודל N. כל ערך חדש נדחף; אם הערימה גדלה מעבר ל-N, נזרק הקטן ביותר. הקטן ביותר נמצא תמיד ב-heap[0], כך שהשוואה בודדת קובעת אם לשמור או לזרוק כל פריט נכנס:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

הערימה אף פעם לא גדלה מעבר ל-N, כך שכל ערך נכנס עולה אותו מספר מצומצם של השוואות לא משנה כמה ארוך הזרם. ה-sorted הסופי הוא הצעד היחיד שעלותו תלויה ב-N ישירות.

2.38.4. אירועים מתוזמנים

תור עדיפויות של זוגות (deadline, payload) הוא הצורה הסטנדרטית למתזמן אירועים. זוגות (tuples) מושווים לקסיקוגרפית, כך שהזוג עם המועד האחרון הקטן ביותר צף אוטומטית לראש:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

אם שני אירועים חולקים אותו מועד אחרון, השוואת הזוג נופלת לאיבר השני. עבור payloads שאינם ניתנים להשוואה באופן טבעי, יש להוסיף מונה כאיבר השני של הזוג כדי לכפות סדר יציב:

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

כעת ההתנהגות של מועד-מוקדם-קודם נשמרת, תיקו נשבר לפי המונה כך שמשימות שתוזמנו מוקדם יותר רצות ראשונות, ו-task אינו חייב להיות ניתן להשוואה.

2.38.5. מה ש-heapq אינו נותן לך

כמה דפוסים שנראה כאילו הם אמורים לעבוד, אך לא:

• מעבר for x in heap אינו מחזיר פלט ממוין – הסדר הבסיסי של הרשימה הוא פריסת העץ של הערימה. כדי לצרוך את הערימה בסדר, יש להפעיל heappop עד שהיא מתרוקנת.

• אין דרך לשנות את העדיפות של פריט שכבר נמצא בערימה. הפתרון הסטנדרטי הוא לדחוף את העדיפות החדשה כרשומה חדשה ולסמן את הישנה כמבוטלת (לדלג עליה כשהיא יוצאת).

• הערימה מאחסנת הפניות לפריטים שלה, לא עותקים. שינוי פריט לאחר שנדחף עלול לשבור את אינוריאנט הערימה. יש להשתמש בערכים בלתי-משתנים (מספרים, זוגות) כמפתח ההשוואה.

min-heap על רשימה רגילה הוא הכלי הנכון לכל שאלה של ”מה הקטן ביותר“ או ”מה הדחוף ביותר“ במכשיר מוטמע קטן. שלוש פונקציות, רשימה אחת, והערימה דואגת לכל השאר.