2.38. Очереди с приоритетом

Очередь с приоритетом – это контейнер, который всегда знает, какой из его элементов наименьший (или наибольший), без сортировки всего содержимого. heapq реализует такую очередь в MicroPython, используя обычный list в качестве хранилища и древовидный алгоритм под названием мин-куча, который держит наименьший элемент по индексу 0.

2.38.1. Концептуальная модель

Мин-куча – это список, организованный так, что элемент по каждому индексу меньше или равен элементам по индексам 2*i + 1 и 2*i + 2. Такая организация делает три операции дешёвыми:

  • Поиск наименьшего элемента – он находится в heap[0]. Один просмотр по индексу, без сканирования.

  • Добавление элемента – оно всплывает вверх по дереву, сравниваясь с одним родителем на каждом уровне. Тысяча элементов – это около десяти сравнений; миллион – около двадцати.

  • Удаление наименьшего элемента – тот же проход в обратном направлении, с тем же небольшим числом сравнений.

Список не отсортирован. При итерации по нему элементы возвращаются в произвольном порядке. Гарантированно наименьшим является только heap[0].

2.38.2. Три функции в MicroPython

Модуль heapq в MicroPython предоставляет ровно три функции:

  • heapq.heappush() – вставить элемент, сохраняя инвариант кучи нетронутым.

  • heapq.heappop() – удалить и вернуть наименьший элемент.

  • heapq.heapify() – перестроить существующий список в кучу на месте.

Это весь набор. Функций heappushpop, heapreplace, nlargest, nsmallest и merge из CPython здесь нет; приведённые ниже шаблоны показывают, как реализовать распространённые из них вручную.

Начало с нуля:

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

Начало с существующих данных:

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

Heapify затрагивает каждый элемент один раз и заметно быстрее, чем добавление тех же элементов по одному.

2.38.3. Top-N по потоку

Естественное применение очереди с приоритетом: отслеживание N наибольших элементов в потоке, который можно прочитать только один раз.

Приём заключается в том, чтобы держать мин-кучу размера N. Каждое новое значение добавляется; если куча вырастает больше N, наименьший элемент отбрасывается. Наименьший элемент всегда находится в heap[0], поэтому одно сравнение решает, сохранить или отбросить каждый поступающий элемент:

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)

Куча никогда не вырастает больше N, поэтому каждое поступающее значение стоит одного и того же небольшого числа сравнений независимо от длины потока. Завершающая операция sorted – единственный шаг, стоимость которого зависит непосредственно от N.

2.38.4. Запланированные события

Очередь с приоритетом из кортежей (deadline, payload) – стандартная форма для планировщика событий. Кортежи сравниваются лексикографически, поэтому кортеж с наименьшим сроком автоматически всплывает наверх:

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)

Если у двух событий совпадают сроки, сравнение кортежей переходит ко второму элементу. Для полезных данных, которые не сравниваются естественным образом, добавьте счётчик в качестве второго элемента кортежа, чтобы обеспечить стабильный порядок:

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

Теперь поведение «наименьший срок первым» сохранено, ничьи разрешаются по счётчику, так что задачи, запланированные раньше, выполняются первыми, а task не обязан быть сравнимым.

2.38.5. Чего heapq вам не даёт

Несколько шаблонов, которые выглядят так, будто должны работать, но не работают:

  • Итерация for x in heap не даёт отсортированный вывод – внутренний порядок списка отражает древовидную структуру кучи. Чтобы получить элементы кучи по порядку, вызывайте heappop, пока она не опустеет.

  • Невозможно изменить приоритет элемента, уже находящегося в куче. Стандартный обходной путь – добавить новый приоритет как новую запись и пометить старую как отменённую (пропустить её, когда она извлекается).

  • Куча хранит ссылки на свои элементы, а не копии. Изменение элемента после его добавления может нарушить инвариант кучи. Используйте неизменяемые значения (числа, кортежи) в качестве ключа сравнения.

Мин-куча на обычном списке – правильный инструмент для любого вопроса вида «что наименьшее» или «что наиболее срочное» на небольшом встраиваемом устройстве. Три функции, один список, и куча берёт на себя всё остальное.