2.38. Prioritetni redovi¶

Prioritetni red je spremnik koji uvijek zna koja je od njegovih stavki najmanja (ili najveća) bez sortiranja cijelog sadržaja. heapq ga u MicroPythonu implementira koristeći običnu list kao pohranu i algoritam temeljen na stablu zvan min-heap koji najmanju stavku drži na indeksu 0.

2.38.1. Mentalni model¶

Min-heap je lista posložena tako da je stavka na svakom indeksu manja ili jednaka stavkama na indeksima 2*i + 1 i 2*i + 2. Takav raspored čini tri operacije jeftinima:

Pronalaženje najmanje stavke – nalazi se na heap[0]. Jedno pretraživanje po indeksu, bez prolaska kroz cijelu listu.
Dodavanje stavke – ona se penje kroz stablo, uspoređujući se s jednim roditeljem po razini. Tisuću stavki znači otprilike deset usporedbi; milijun ih je otprilike dvadeset.
Uklanjanje najmanje stavke – isti hod u obrnutom smjeru, s istom šačicom usporedbi.

Lista nije sortirana. Iteriranje po njoj daje stavke proizvoljnim redoslijedom. Samo je za heap[0] zajamčeno da je minimum.

2.38.2. Tri funkcije u MicroPythonu¶

MicroPythonov heapq izlaže točno tri funkcije:

heapq.heappush() – umeće stavku, čuvajući invarijantu heapa netaknutom.
heapq.heappop() – uklanja i vraća najmanju stavku.
heapq.heapify() – preuređuje postojeću listu u heap na mjestu.

To je cijela površina. CPythonovi heappushpop, heapreplace, nlargest, nsmallest i merge ne postoje; primjeri u nastavku pokazuju kako uobičajene izgraditi ručno.

Početak iz čista lista:

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

Početak od postojećih podataka:

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

Heapifikacija dotiče svaku stavku jednom i osjetno je brža od dodavanja istih stavki jedne po jedne.

2.38.3. Najboljih N preko toka podataka¶

Prirodna upotreba prioritetnog reda: praćenje N najvećih stavki u toku podataka koji možeš pročitati samo jednom.

Trik je u tome da držiš min-heap veličine N. Svaka nova vrijednost se gurne; ako heap naraste preko N, izbaci se najmanja. Najmanja je uvijek na heap[0], pa jedna usporedba odlučuje hoće li se svaka dolazeća stavka zadržati ili odbaciti:

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)

Heap nikad ne naraste preko N, pa svaka dolazeća vrijednost košta istu šačicu usporedbi bez obzira na to koliko je tok dugačak. Završni sorted jedini je korak čiji trošak izravno ovisi o N.

2.38.4. Zakazani događaji¶

Prioritetni red (deadline, payload) n-torki standardni je oblik za raspoređivač događaja. N-torke se uspoređuju leksikografski, pa n-torka s najmanjim rokom automatski isplivava na vrh:

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)

Ako dva događaja dijele isti rok, usporedba n-torki pada na drugi element. Za podatke koji nisu prirodno usporedivi, dodaj brojač kao drugi element n-torke kako bi se nametnuo stabilan redoslijed:

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

Sada je ponašanje „najmanji rok prvi” netaknuto, izjednačenja se razrješavaju po brojaču pa se ranije zakazani zadaci izvršavaju prvi, a task ne mora biti usporediv.

2.38.5. Što ti `heapq` ne pruža¶

Nekoliko obrazaca koji izgledaju kao da bi trebali raditi, ali ne rade:

Iteriranje for x in heap ne daje sortirani izlaz – temeljni redoslijed liste je raspored stabla heapa. Da bi heap konzumirao po redu, radi heappop dok se ne isprazni.
Ne postoji način da se promijeni prioritet stavke koja je već u heapu. Standardno zaobilazno rješenje je gurnuti novi prioritet kao novi unos i označiti stari kao otkazan (preskoči ga kad ispliva).
Heap pohranjuje reference na svoje stavke, ne kopije. Mijenjanje stavke nakon što je gurnuta može narušiti invarijantu heapa. Koristi nepromjenjive vrijednosti (brojeve, n-torke) kao ključ usporedbe.

Min-heap na običnoj listi pravi je alat za svako pitanje „što je najmanje” ili „što je najhitnije” na malom ugradbenom uređaju. Tri funkcije, jedna lista, a heap se brine za ostalo.