2.38. Prioriteitswachtrijen

Een prioriteitswachtrij is een container die altijd weet welk van zijn items het kleinste (of het grootste) is, zonder het geheel te sorteren. heapq implementeert er een in MicroPython met behulp van een gewone list als opslag en een boomgebaseerd algoritme genaamd een min-heap om het kleinste item op index 0 te houden.

2.38.1. Het mentale model

Een min-heap is een lijst die zo is gerangschikt dat het item op elke index kleiner-dan-of-gelijk-aan de items op de indices 2*i + 1 en 2*i + 2 is. Die rangschikking maakt drie bewerkingen goedkoop:

• Het kleinste item vinden – het bevindt zich op heap[0]. Een enkele indexopzoeking, geen scan.

• Een item toevoegen – het borrelt omhoog door de boom, en wordt per niveau met één ouder vergeleken. Duizend items kost ongeveer tien vergelijkingen; een miljoen ongeveer twintig.

• Het kleinste item verwijderen – dezelfde wandeling in omgekeerde richting, met hetzelfde handjevol vergelijkingen.

De lijst is niet gesorteerd. Erover itereren levert de items in willekeurige volgorde op. Alleen heap[0] is gegarandeerd het minimum.

2.38.2. De drie functies in MicroPython

MicroPython’s heapq stelt precies drie functies beschikbaar:

• heapq.heappush() – voeg een item in en houd de heap-invariant intact.

• heapq.heappop() – verwijder het kleinste item en geef het terug.

• heapq.heapify() – herschik een bestaande lijst ter plaatse tot een heap.

Dat is het volledige oppervlak. CPython’s heappushpop, heapreplace, nlargest, nsmallest en merge bestaan niet; de onderstaande patronen laten zien hoe je de meest voorkomende met de hand bouwt.

Helemaal opnieuw beginnen:

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

Beginnen vanaf bestaande gegevens:

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

Heapify raakt elk item één keer aan en is merkbaar sneller dan dezelfde items één voor één pushen.

2.38.3. Top-N over een stream

Een natuurlijk gebruik van een prioriteitswachtrij: de N grootste items bijhouden in een stream die je maar één keer kunt lezen.

De truc is om een min-heap van grootte N aan te houden. Elke nieuwe waarde wordt gepusht; als de heap groter wordt dan N, laat dan het kleinste vallen. Het kleinste staat altijd op heap[0], dus een enkele vergelijking beslist of elk binnenkomend item wordt behouden of weggegooid:

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)

De heap groeit nooit voorbij N, dus elke binnenkomende waarde kost hetzelfde handjevol vergelijkingen, ongeacht hoe lang de stream is. De uiteindelijke sorted is de enige stap waarvan de kosten rechtstreeks van N afhangen.

2.38.4. Geplande gebeurtenissen

Een prioriteitswachtrij van (deadline, payload)-tuples is de standaardvorm voor een gebeurtenisplanner. Tuples worden lexicografisch vergeleken, zodat de tuple met de kleinste deadline automatisch naar boven drijft:

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)

Als twee gebeurtenissen een deadline delen, valt de tuplevergelijking door naar het tweede element. Voeg voor payloads die niet van nature vergelijkbaar zijn een teller toe als tweede element van de tuple om een stabiele ordening af te dwingen:

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

Nu is het gedrag van kleinste-deadline-eerst intact, gelijkspel wordt beslist op de teller zodat eerder geplande taken eerst draaien, en task hoeft niet vergelijkbaar te zijn.

2.38.5. Wat heapq je niet biedt

Een paar patronen die lijken te moeten werken, maar dat niet doen:

• Itereren met for x in heap levert geen gesorteerde uitvoer op – de onderliggende volgorde van de lijst is de boomstructuur van de heap. Om de heap in volgorde te verbruiken, gebruik je heappop totdat hij leeg is.

• Er is geen manier om de prioriteit van een item dat al in de heap zit te wijzigen. De standaardoplossing is om de nieuwe prioriteit als een verse vermelding te pushen en de oude als geannuleerd te markeren (sla die over wanneer hij eruit komt).

• De heap slaat verwijzingen naar zijn items op, geen kopieën. Een item muteren nadat het is gepusht kan de heap-invariant breken. Gebruik onveranderlijke waarden (getallen, tuples) als vergelijkingssleutel.

Een min-heap op een gewone lijst is het juiste gereedschap voor elke vraag van “wat is het kleinste” of “wat is het meest urgente” op een klein embedded apparaat. Drie functies, één lijst, en de heap regelt de rest.