2.38. Prioritní fronty¶

Prioritní fronta je kontejner, který vždy ví, která z jeho položek je nejmenší (nebo největší), aniž by se musel celý setřídit. heapq jednu takovou v MicroPythonu implementuje s využitím obyčejného list jako úložiště a stromového algoritmu zvaného min-heap, který udržuje nejmenší položku na indexu 0.

2.38.1. Mentální model¶

Min-heap je seznam uspořádaný tak, že položka na každém indexu je menší nebo rovna položkám na indexech 2*i + 1 a 2*i + 2. Díky tomuto uspořádání jsou tři operace levné:

Nalezení nejmenší položky – je na heap[0]. Jediné vyhledání podle indexu, žádné procházení.
Přidání položky – probublá nahoru skrz strom a na každé úrovni se porovná s jedním rodičem. Tisíc položek znamená asi deset porovnání; milion asi dvacet.
Odebrání nejmenší položky – stejná cesta opačným směrem se stejnou hrstkou porovnání.

Seznam není setříděný. Iterace přes něj vrací položky v libovolném pořadí. Pouze u heap[0] je zaručeno, že jde o minimum.

2.38.2. Tři funkce v MicroPythonu¶

MicroPythonový heapq zpřístupňuje přesně tři funkce:

heapq.heappush() – vloží položku a přitom zachová invariant haldy.
heapq.heappop() – odebere a vrátí nejmenší položku.
heapq.heapify() – přeuspořádá existující seznam na haldu na místě.

To je celý rozsah. CPythonové heappushpop, heapreplace, nlargest, nsmallest a merge neexistují; vzory níže ukazují, jak ty běžné z nich postavit ručně.

Začínáme od nuly:

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

Začínáme z existujících dat:

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

Heapifikace se dotkne každé položky jednou a je znatelně rychlejší než vkládání stejných položek po jedné.

2.38.3. Top-N nad proudem¶

Přirozené využití prioritní fronty: sledování N největších položek v proudu, který lze přečíst jen jednou.

Trik spočívá v udržování min-heap o velikosti N. Každá nová hodnota se vloží; pokud halda přeroste N, odebere se nejmenší. Nejmenší je vždy na heap[0], takže o tom, zda každou příchozí položku ponechat nebo zahodit, rozhodne jediné porovnání:

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)

Halda nikdy nepřeroste N, takže každá příchozí hodnota stojí stejnou hrstku porovnání bez ohledu na to, jak dlouhý proud je. Závěrečné sorted je jediný krok, jehož cena závisí přímo na N.

2.38.4. Naplánované události¶

Prioritní fronta dvojic (deadline, payload) je standardní podoba plánovače událostí. Dvojice se porovnávají lexikograficky, takže dvojice s nejmenším termínem vyplave automaticky na vrchol:

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)

Pokud dvě události sdílejí termín, porovnání dvojic propadne na druhý prvek. U dat (payload), která nelze přirozeně porovnat, přidejte jako druhý prvek dvojice čítač, abyste vynutili stabilní řazení:

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

Nyní je chování „nejmenší termín první“ zachováno, shody se rozhodnou podle čítače, takže dříve naplánované úlohy se spustí jako první, a task nemusí být porovnatelná.

2.38.5. Co vám `heapq` neposkytuje¶

Několik vzorů, které vypadají, že by měly fungovat, ale nefungují:

Iterace for x in heap nevrací setříděný výstup – vnitřní pořadí seznamu je stromové rozvržení haldy. Chcete-li haldu zkonzumovat v pořadí, volejte heappop, dokud není prázdná.
Není možné změnit prioritu položky, která už v haldě je. Standardní řešení je vložit novou prioritu jako čerstvou položku a tu starou označit jako zrušenou (přeskočit ji, až vyskočí).
Halda ukládá odkazy na své položky, nikoli kopie. Mutace položky po jejím vložení může porušit invariant haldy. Jako porovnávací klíč používejte neměnné hodnoty (čísla, dvojice).

Min-heap nad obyčejným seznamem je ten správný nástroj pro jakoukoli otázku typu „co je nejmenší“ nebo „co je nejnaléhavější“ na malém vestavěném zařízení. Tři funkce, jeden seznam a o zbytek se postará halda.