2.38. Prioritetsköer¶

En prioritetskö är en behållare som alltid vet vilket av dess element som är det minsta (eller det största) utan att sortera hela samlingen. heapq implementerar en sådan i MicroPython med hjälp av en vanlig list som lagring och en trädbaserad algoritm som kallas min-heap för att hålla det minsta elementet vid index 0.

2.38.1. Den mentala modellen¶

En min-heap är en lista ordnad så att elementet vid varje index är mindre-än-eller-lika-med elementen vid index 2*i + 1 och 2*i + 2. Den ordningen gör tre operationer billiga:

Att hitta det minsta elementet – det finns vid heap[0]. En enda indexuppslagning, ingen genomsökning.
Att lägga till ett element – det bubblar uppåt genom trädet och jämförs mot en förälder per nivå. Tusen element kräver ungefär tio jämförelser; en miljon ungefär tjugo.
Att ta bort det minsta elementet – samma vandring fast omvänt, med samma handfull jämförelser.

Listan är inte sorterad. Att iterera över den ger elementen i godtycklig ordning. Endast heap[0] garanteras vara minimumet.

2.38.2. De tre funktionerna i MicroPython¶

MicroPythons heapq exponerar exakt tre funktioner:

heapq.heappush() – infogar ett element och bevarar heap-invarianten intakt.
heapq.heappop() – tar bort och returnerar det minsta elementet.
heapq.heapify() – omordnar en befintlig lista till en heap på plats.

Det är hela ytan. CPythons heappushpop, heapreplace, nlargest, nsmallest och merge finns inte; mönstren nedan visar hur du bygger de vanligaste för hand.

Starta från början:

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

Starta från befintliga data:

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

Att heapifiera berör varje element en gång och är märkbart snabbare än att lägga in samma element ett i taget.

2.38.3. Topp-N över en ström¶

En naturlig användning av en prioritetskö: håll reda på de N största elementen i en ström som du bara kan läsa en gång.

Knepet är att hålla en min-heap av storlek N. Varje nytt värde läggs in; om heapen växer förbi N tas det minsta bort. Det minsta finns alltid vid heap[0], så en enda jämförelse avgör om varje inkommande element ska behållas eller kastas:

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)

Heapen växer aldrig förbi N, så varje inkommande värde kostar samma handfull jämförelser oavsett hur lång strömmen är. Den avslutande sorted är det enda steget vars kostnad beror direkt på N.

2.38.4. Schemalagda händelser¶

En prioritetskö av (deadline, payload)-tupler är standardformen för en händelseschemaläggare. Tupler jämförs lexikografiskt, så tupeln med den minsta deadlinen flyter automatiskt upp till toppen:

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)

Om två händelser delar samma deadline går tupeljämförelsen vidare till det andra elementet. För nyttolaster som inte är naturligt jämförbara, lägg till en räknare som tupelns andra element för att framtvinga en stabil ordning:

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

Nu är beteendet minsta-deadline-först intakt, lika deadlines bryts på räknaren så att tidigare schemalagda uppgifter körs först, och task behöver inte vara jämförbar.

2.38.5. Vad `heapq` inte ger dig¶

Några få mönster som ser ut som om de borde fungera, men inte gör det:

Att iterera for x in heap ger inte sorterad utmatning – listans underliggande ordning är heapens trädlayout. För att konsumera heapen i ordning, kör heappop tills den är tom.
Det finns inget sätt att ändra prioriteten för ett element som redan finns i heapen. Den vanliga lösningen är att lägga in den nya prioriteten som en ny post och markera den gamla som avbruten (hoppa över den när den dyker upp).
Heapen lagrar referenser till sina element, inte kopior. Att mutera ett element efter att det lagts in kan bryta heap-invarianten. Använd oföränderliga värden (tal, tupler) som jämförelsenyckel.

En min-heap på en vanlig lista är rätt verktyg för alla frågor av typen ”vad är minst” eller ”vad är mest brådskande” på en liten inbäddad enhet. Tre funktioner, en lista, och heapen sköter resten.