Kopce i kolejki priorytetowe: heapq, schedulery i token bucket

Wszystkie struktury z tej serii utrzymywały porządek: tablica mieszająca żaden, drzewa i B-drzewa pełny. Kopiec siedzi pomiędzy: pilnuje tylko jednej rzeczy – żeby na wierzchu był element najmniejszy (albo największy). O resztę nie dba.

Ta pozorna skromność jest jego siłą. Utrzymanie pełnego porządku kosztuje przy każdej zmianie; utrzymanie jednego elementu na wierzchu kosztuje logarytm – a bardzo często to wszystko, czego potrzebujemy.

Drzewo, które jest tablicą

Kopiec binarny to drzewo z jednym warunkiem: rodzic jest nie większy od swoich dzieci (w kopcu minimalnym). Nie ma warunku między rodzeństwem – i dlatego drzewo jest zawsze pełne, a skoro jest pełne, nie potrzebuje wskaźników. Wystarczy tablica i arytmetyka indeksów:

• dzieci węzła i leżą pod 2i + 1 i 2i + 2,
• rodzic węzła i pod (i - 1) // 2.

Zero obiektów, zero skoków po pamięci – dane leżą ciasno obok siebie, co procesor bardzo lubi. Poniżej animacja z serii o sortowaniu, pokazująca kopiec od strony sortowania przez kopcowanie: najpierw budowa kopca, potem zdejmowanie maksimum na koniec tablicy.

Dwie operacje wystarczą, żeby to działało:

# Python
def sift_up(heap, index):
    """Nowy element wędruje w górę, dopóki jest mniejszy od rodzica."""
    while index > 0:
        parent = (index - 1) // 2
        if heap[parent] <= heap[index]:
            break
        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent


def sift_down(heap, index, size):
    """Element ze szczytu opada, zamieniając się z mniejszym z dzieci."""
    while True:
        left, right = 2 * index + 1, 2 * index + 2
        smallest = index
        if left < size and heap[left] < heap[smallest]:
            smallest = left
        if right < size and heap[right] < heap[smallest]:
            smallest = right
        if smallest == index:
            return
        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest

Wstawienie to dopisanie na koniec i sift_up – O(log n). Zdjęcie szczytu to podmiana z ostatnim elementem, skrócenie tablicy i sift_down – też O(log n). Podejrzenie najmniejszego elementu: O(1), bo leży pod indeksem zero.

Ciekawostka, która zaskakuje: zbudowanie kopca z gotowej tablicy kosztuje O(n), a nie O(n log n). Wystarczy wywołać sift_down od połowy tablicy w dół – większość elementów to liście, które nie mają dokąd opadać, więc suma kosztów zbiega się do liniowej.

heapq: kopiec, który już masz

Python nie ma klasy kopca – ma moduł heapq operujący na zwykłej liście:

# Python
import heapq

zadania = []
heapq.heappush(zadania, (3, "wyślij raport"))
heapq.heappush(zadania, (1, "zresetuj hasło"))
heapq.heappush(zadania, (2, "wygeneruj fakturę"))

heapq.heappop(zadania)        # (1, 'zresetuj hasło') – zawsze najpilniejsze
zadania[0]                    # podejrzenie bez zdejmowania, O(1)

liczby = [7, 2, 9, 4, 1]
heapq.heapify(liczby)         # O(n), w miejscu

Trzy rzeczy warte zapamiętania:

• heapq jest kopcem minimalnym. Dla maksymalnego wstawiaj priorytety ze znakiem minus albo trzymaj krotki (-priorytet, dane).
• Krotki porównują się po kolei, więc (priorytet, licznik, dane) to standardowy trik: licznik rozstrzyga remisy w kolejności zgłoszeń (dokładnie ta sama sztuczka, którą PHP 8.0 zrobiło ze stabilnością sortowania) i chroni przed porównywaniem obiektów, które porównywać się nie potrafią.
• heapq nie jest bezpieczny wątkowo. Od tego jest queue.PriorityQueue, który opakowuje ten sam kopiec w blokady.

Po co to komu: cztery zastosowania

1. K największych bez sortowania

Klasyczne zadanie: dziesięć najdroższych zamówień z miliona. Sortowanie całości to O(n log n). Kopiec o rozmiarze k daje O(n log k) – przechodzisz dane raz, trzymając w kopcu tylko dziesięć najlepszych kandydatów.

# Python
import heapq

najwieksze = heapq.nlargest(10, zamowienia, key=lambda z: z.kwota)

Dla miliona elementów i k = 10 różnica w liczbie porównań to około 20 mln kontra 3,3 mln – i, co ważniejsze, pamięć rzędu dziesięciu elementów zamiast miliona. To ta sama zasada, którą kończyła się seria o sortowaniu: najlepszym sortowaniem bywa jego brak.

2. Scalanie strumieni większych niż pamięć

# Python
import heapq
from contextlib import ExitStack

def scal_posortowane_pliki(sciezki):
    """k-way merge: kopiec trzyma po jednym wierszu z każdego pliku."""
    with ExitStack() as stack:
        pliki = [stack.enter_context(open(s, encoding="utf-8")) for s in sciezki]
        for wiersz in heapq.merge(*pliki):     # leniwe, nie ładuje całości do pamięci
            yield wiersz

heapq.merge to serce sortowania zewnętrznego: dzielisz plik na porcje mieszczące się w pamięci, sortujesz każdą, a potem scalasz je wszystkie naraz, trzymając w kopcu tylko po jednym elemencie z każdej porcji. Dokładnie tak działa uniksowy sort na pliku większym niż RAM.

3. Scheduler i timery

Każdy system, który ma „wykonaj to o 14:30”, trzyma zadania w kopcu uporządkowanym po czasie. Pętla zdarzeń nie przegląda listy – patrzy na szczyt kopca, oblicza, ile zostało do najbliższego terminu, i śpi dokładnie tyle. Tak działa sched w Pythonie, timery w pętlach zdarzeń i kolejki zadań w Celery czy w systemach kolejkowych.

4. Ogranicznik ruchu

Kopiec nie jest tu konieczny, ale ten sam sposób myślenia – „koszt teraz, budżet na przyszłość” – daje token bucket, najpopularniejszy algorytm ograniczania liczby żądań:

# Python
import time

class TokenBucket:
    """Wiadro napełnia się w stałym tempie; żądanie kosztuje jeden żeton."""

    def __init__(self, capacity, refill_per_second):
        self.capacity = capacity
        self.refill = refill_per_second
        self.tokens = capacity
        self.checked_at = time.monotonic()

    def allow(self, cost=1):
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.checked_at) * self.refill)
        self.checked_at = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False        # 429 Too Many Requests

Piękno tego rozwiązania polega na tym, że nie trzyma historii żądań – wystarczy liczba żetonów i znacznik czasu ostatniego sprawdzenia. Pojemność wiadra pozwala na krótkie zrywy, a tempo napełniania ustala średnią. To praktyczna kontynuacja wątku z wpisu o złożoności jako podatności: skoro jedno żądanie może kosztować serwer sekundy, trzeba ograniczyć, ile ich wpuszczamy.

Podsumowanie

Kopiec jest optymalny dokładnie wtedy, gdy interesuje cię skrajność, a nie porządek. Jeśli zaczniesz pytać go o środek zbioru, przegrywa z każdą inną strukturą z tej serii.

W ostatniej części serii kopiec wróci w roli, dla której najczęściej się go używa: jako kolejka priorytetowa w algorytmie Dijkstry, czyli w tym, co liczy trasę na mapie.