2.38. Черги з пріоритетом¶

Черга з пріоритетом — це контейнер, який завжди знає, який з його елементів є найменшим (або найбільшим), не сортуючи весь список. heapq реалізує таку чергу в MicroPython, використовуючи звичайний list як сховище та алгоритм на основі дерева, що називається мінімальною купою (min-heap), щоб зберігати найменший елемент на індексі 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() – перетворити існуючий список на купу «на місці».

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

Початок з нуля:

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

Перетворення на купу торкається кожного елемента один раз і помітно швидше, ніж послідовне додавання тих самих елементів по одному.

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 до спустошення.
Немає способу змінити пріоритет елемента, що вже знаходиться в купі. Стандартний обхідний шлях — додати новий пріоритет як новий запис і позначити старий як скасований (пропустити його при вилученні).
Купа зберігає посилання на свої елементи, а не їхні копії. Зміна елемента після його додавання може порушити властивість купи. Використовуйте незмінні значення (числа, кортежі) як ключ порівняння.

Мінімальна купа на простому списку — це правильний інструмент для будь-якого питання «що найменше» або «що найбільш термінове» на невеликому вбудованому пристрої. Три функції, один список — і купа бере на себе все інше.