2.38. Kolejki priorytetowe¶

Kolejka priorytetowa to kontener, który zawsze wie, który z jego elementów jest najmniejszy (lub największy), bez sortowania całości. heapq implementuje taką kolejkę w MicroPython, używając zwykłej list jako magazynu oraz drzewiastego algorytmu zwanego kopcem minimum (min-heap), który utrzymuje najmniejszy element pod indeksem 0.

2.38.1. Model myślowy¶

Kopiec minimum to lista ułożona tak, że element pod każdym indeksem jest mniejszy lub równy elementom pod indeksami 2*i + 1 i 2*i + 2. Takie ułożenie sprawia, że trzy operacje są tanie:

Znalezienie najmniejszego elementu – znajduje się pod heap[0]. Pojedyncze odczytanie indeksu, bez przeszukiwania.
Dodanie elementu – przemieszcza się on w górę drzewa, porównując się z jednym rodzicem na każdym poziomie. Tysiąc elementów to około dziesięciu porównań; milion to około dwudziestu.
Usunięcie najmniejszego elementu – ten sam ruch w odwrotną stronę, z tą samą garstką porównań.

Lista nie jest posortowana. Iterowanie po niej zwraca elementy w dowolnej kolejności. Jedynie heap[0] ma gwarancję bycia minimum.

2.38.2. Trzy funkcje w MicroPython¶

Moduł heapq w MicroPython udostępnia dokładnie trzy funkcje:

heapq.heappush() – wstawia element, zachowując nienaruszony niezmiennik kopca.
heapq.heappop() – usuwa i zwraca najmniejszy element.
heapq.heapify() – przekształca istniejącą listę w kopiec w miejscu.

To cała dostępna powierzchnia. Znane z CPython heappushpop, heapreplace, nlargest, nsmallest oraz merge nie istnieją; poniższe wzorce pokazują, jak ręcznie zbudować te najczęściej używane.

Zaczynając od zera:

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

Zaczynając od istniejących danych:

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

Heapify dotyka każdego elementu raz i jest zauważalnie szybsze niż dodawanie tych samych elementów pojedynczo.

2.38.3. Top-N nad strumieniem¶

Naturalne zastosowanie kolejki priorytetowej: śledzenie N największych elementów w strumieniu, który można odczytać tylko raz.

Sztuczka polega na utrzymywaniu kopca minimum o rozmiarze N. Każda nowa wartość jest dodawana; jeśli kopiec urośnie powyżej N, usuwany jest najmniejszy element. Najmniejszy zawsze znajduje się pod heap[0], więc pojedyncze porównanie decyduje, czy zachować, czy odrzucić każdy napływający element:

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)

Kopiec nigdy nie rośnie powyżej N, więc każda napływająca wartość kosztuje tę samą garstkę porównań niezależnie od długości strumienia. Końcowe sorted to jedyny krok, którego koszt zależy bezpośrednio od N.

2.38.4. Zaplanowane zdarzenia¶

Kolejka priorytetowa krotek (deadline, payload) to standardowa forma harmonogramu zdarzeń. Krotki porównują się leksykograficznie, więc krotka z najmniejszym terminem automatycznie wypływa na szczyt:

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)

Jeśli dwa zdarzenia mają ten sam termin, porównanie krotek przechodzi do drugiego elementu. W przypadku ładunków, które nie są w naturalny sposób porównywalne, dodaj licznik jako drugi element krotki, aby wymusić stabilne uporządkowanie:

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

Teraz zachowanie typu najmniejszy-termin-najpierw pozostaje nienaruszone, remisy rozstrzyga licznik, dzięki czemu wcześniej zaplanowane zadania uruchamiają się jako pierwsze, a task nie musi być porównywalny.

2.38.5. Czego `heapq` ci nie daje¶

Kilka wzorców, które wyglądają, jakby powinny działać, ale nie działają:

Iterowanie for x in heap nie daje posortowanego wyniku – bazowa kolejność listy to drzewiasty układ kopca. Aby skonsumować kopiec w kolejności, wywołuj heappop aż do opróżnienia.
Nie ma sposobu na zmianę priorytetu elementu już znajdującego się w kopcu. Standardowe obejście polega na dodaniu nowego priorytetu jako świeżego wpisu i oznaczeniu starego jako anulowanego (pominięcie go, gdy wyskoczy).
Kopiec przechowuje odwołania do swoich elementów, a nie kopie. Modyfikacja elementu po jego dodaniu może naruszyć niezmiennik kopca. Używaj niemutowalnych wartości (liczb, krotek) jako klucza porównania.

Kopiec minimum na zwykłej liście to właściwe narzędzie do każdego pytania typu „co jest najmniejsze” lub „co jest najpilniejsze” na małym urządzeniu wbudowanym. Trzy funkcje, jedna lista, a kopiec zajmuje się resztą.