2.38. Prioritási sorok¶

A prioritási sor olyan tároló, amely mindig tudja, melyik eleme a legkisebb (vagy a legnagyobb) anélkül, hogy az egészet rendezné. A heapq egy ilyet valósít meg a MicroPythonban: tárolóként egy egyszerű list típust használ, és egy min-heap nevű, fa alapú algoritmussal tartja a legkisebb elemet a 0. indexen.

2.38.1. A gondolati modell¶

A min-heap egy úgy elrendezett lista, amelyben minden index elemén lévő érték kisebb vagy egyenlő a 2*i + 1 és 2*i + 2 indexeken lévő elemeknél. Ez az elrendezés három műveletet tesz olcsóvá:

A legkisebb elem megtalálása – a heap[0] helyen van. Egyetlen indexes kikeresés, semmilyen végigjárás.
Egy elem hozzáadása – felbugyog a fán, szintenként egy szülővel összehasonlítva. Ezer elem körülbelül tíz összehasonlítás; egymillió körülbelül húsz.
A legkisebb elem eltávolítása – ugyanaz a bejárás fordítva, ugyanazzal a maréknyi összehasonlítással.

A lista nincs rendezve. Végigiterálva rajta tetszőleges sorrendben kapod meg az elemeket. Csak a heap[0] garantáltan a minimum.

2.38.2. A három függvény a MicroPythonban¶

A MicroPython heapq modulja pontosan három függvényt tesz elérhetővé:

heapq.heappush() – beszúr egy elemet, miközben sértetlenül megtartja a heap-invariánst.
heapq.heappop() – eltávolítja és visszaadja a legkisebb elemet.
heapq.heapify() – egy meglévő listát helyben heappé rendez át.

Ennyi a teljes felület. A CPython heappushpop, heapreplace, nlargest, nsmallest és merge függvényei nem léteznek; az alábbi minták megmutatják, hogyan építsd fel a leggyakoribbakat kézzel.

Üres lapról indulva:

>>> 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

Meglévő adatokból indulva:

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

A heapesítés minden elemet egyszer érint, és észrevehetően gyorsabb, mint ugyanazokat az elemeket egyesével betolni.

2.38.3. Top-N egy adatfolyamon¶

A prioritási sor egy természetes felhasználása: kövesd az N legnagyobb elemet egy adatfolyamban, amelyet csak egyszer tudsz beolvasni.

A trükk az, hogy tarts egy N méretű min-heapet. Minden új érték betolódik; ha a heap N fölé nő, dobd el a legkisebbet. A legkisebb mindig a heap[0] helyen van, így egyetlen összehasonlítás eldönti, hogy megtartsd-e vagy eldobd-e az egyes beérkező elemeket:

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)

A heap soha nem nő N fölé, így minden beérkező érték ugyanannyi maréknyi összehasonlításba kerül, bármilyen hosszú is az adatfolyam. A záró sorted az egyetlen lépés, amelynek költsége közvetlenül N-től függ.

2.38.4. Ütemezett események¶

A (deadline, payload) tuple-ökből álló prioritási sor az eseményütemező szabványos formája. A tuple-ök lexikografikusan hasonlítódnak össze, így a legkisebb határidejű tuple automatikusan a tetejére úszik:

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)

Ha két esemény azonos határidőn osztozik, a tuple-összehasonlítás a második elemre esik át. Az olyan payloadokhoz, amelyek természetüknél fogva nem összehasonlíthatók, adj egy számlálót a tuple második elemeként, hogy stabil sorrendet kényszeríts ki:

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

Most a legkisebb-határidő-először viselkedés sértetlen, a holtversenyek a számláló alapján dőlnek el, így a korábban ütemezett feladatok futnak előbb, és a task nem kell, hogy összehasonlítható legyen.

2.38.5. Amit a `heapq` nem ad meg neked¶

Néhány minta, amely úgy néz ki, mintha működnie kellene, de nem:

A for x in heap iterálás nem ad rendezett kimenetet – a lista mögöttes sorrendje a heap fa-elrendezése. Ha sorrendben akarod feldolgozni a heapet, heappop műveletekkel ürítsd ki.
Nincs mód egy már a heapben lévő elem prioritásának megváltoztatására. A szokásos megkerülő megoldás, hogy az új prioritást új bejegyzésként betolod, a régit pedig törölve-jelölöd (kihagyod, amikor kibukik).
A heap az elemeire való hivatkozásokat tárolja, nem másolatokat. Egy elem módosítása a betolása után megsértheti a heap-invariánst. Használj megváltoztathatatlan értékeket (számokat, tuple-öket) összehasonlítási kulcsként.

Egy egyszerű listán működő min-heap a megfelelő eszköz bármilyen „mi a legkisebb” vagy „mi a legsürgősebb” kérdésre egy kis beágyazott eszközön. Három függvény, egy lista, a többiről pedig a heap gondoskodik.