2.38. Cozi de prioritate¶

O coadă de prioritate este un container care știe întotdeauna care dintre elementele sale este cel mai mic (sau cel mai mare) fără a sorta întreaga colecție. heapq implementează una în MicroPython folosind o simplă list drept stocare și un algoritm bazat pe arbore numit min-heap pentru a menține cel mai mic element la indicele 0.

2.38.1. Modelul mental¶

Un min-heap este o listă aranjată astfel încât elementul de la fiecare indice să fie mai mic sau egal cu elementele de la indicii 2*i + 1 și 2*i + 2. Acel aranjament face ieftine trei operații:

Găsirea celui mai mic element – se află la heap[0]. O singură căutare după indice, fără parcurgere.
Adăugarea unui element – acesta urcă prin arbore, comparându-se cu un singur părinte pe fiecare nivel. O mie de elemente înseamnă aproximativ zece comparații; un milion înseamnă aproximativ douăzeci.
Eliminarea celui mai mic element – aceeași parcurgere în sens invers, cu același număr restrâns de comparații.

Lista nu este sortată. Iterarea peste ea returnează elementele într-o ordine arbitrară. Doar heap[0] este garantat a fi minimul.

2.38.2. Cele trei funcții din MicroPython¶

heapq din MicroPython expune exact trei funcții:

heapq.heappush() – inserează un element, păstrând intact invariantul heap-ului.
heapq.heappop() – elimină și returnează cel mai mic element.
heapq.heapify() – rearanjează pe loc o listă existentă într-un heap.

Aceasta este întreaga interfață. heappushpop, heapreplace, nlargest, nsmallest și merge din CPython nu există; tiparele de mai jos arată cum să le construiești manual pe cele uzuale.

Pornind de la zero:

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

Pornind de la date existente:

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

Transformarea în heap atinge fiecare element o singură dată și este vizibil mai rapidă decât adăugarea acelorași elemente unul câte unul.

2.38.3. Top-N peste un flux¶

O utilizare firească a unei cozi de prioritate: urmărirea celor mai mari N elemente dintr-un flux pe care îl poți citi o singură dată.

Trucul este să menții un min-heap de dimensiune N. Fiecare valoare nouă este adăugată; dacă heap-ul depășește N, se elimină cel mai mic element. Cel mai mic se află întotdeauna la heap[0], așa că o singură comparație decide dacă fiecare element nou este păstrat sau eliminat:

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-ul nu depășește niciodată N, deci fiecare valoare care intră costă același număr restrâns de comparații, indiferent cât de lung este fluxul. Etapa finală sorted este singura al cărei cost depinde direct de N.

2.38.4. Evenimente programate¶

O coadă de prioritate cu tupluri (deadline, payload) este forma standard pentru un programator de evenimente. Tuplurile se compară lexicografic, așa că tuplul cu cel mai mic termen-limită urcă automat în vârf:

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)

Dacă două evenimente au același termen-limită, comparația tuplurilor trece la al doilea element. Pentru sarcini utile care nu sunt comparabile în mod natural, adaugă un contor ca al doilea element al tuplului pentru a forța o ordonare stabilă:

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

Acum comportamentul de tip cel-mai-mic-termen-limită-primul rămâne intact, egalitățile se departajează după contor, astfel încât sarcinile programate mai devreme rulează primele, iar task nu trebuie să fie comparabil.

2.38.5. Ce nu îți oferă `heapq`¶

Câteva tipare care par că ar trebui să funcționeze, dar nu o fac:

Iterarea cu for x in heap nu produce o ieșire sortată – ordinea internă a listei reflectă structura de arbore a heap-ului. Pentru a consuma heap-ul în ordine, apelează heappop până când este gol.
Nu există nicio modalitate de a schimba prioritatea unui element aflat deja în heap. Soluția de rezolvare standard este să adaugi noua prioritate ca o intrare nouă și să marchezi intrarea veche drept anulată (sărind peste ea când este extrasă).
Heap-ul stochează referințe către elementele sale, nu copii. Modificarea unui element după ce a fost adăugat poate strica invariantul heap-ului. Folosește valori imuabile (numere, tupluri) drept cheie de comparație.

Un min-heap pe o listă obișnuită este instrumentul potrivit pentru orice întrebare de tipul „care este cel mai mic” sau „care este cel mai urgent” pe un dispozitiv embedded de dimensiuni mici. Trei funcții, o listă, iar heap-ul se ocupă de restul.