heapq — Алгоритм очереди с приоритетами

Основные примеры

Сортировку с использованием кучи можно реализовать, добавив все значения в кучу, а затем последовательно извлекая наименьшие значения:

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Это похоже на sorted(iterable), но в отличие от sorted(), эта реализация не устойчива.

Элементы кучи могут быть кортежами. Это полезно для присвоения значений сравнения (например, приоритетов задач) наряду с основной отслеживаемой записью:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

Примечания по реализации очереди с приоритетами

Очередь с приоритетами — это распространённое применение кучи, и она представляет ряд проблем с точки зрения реализации:

• Устойчивость сортировки: как получить две задачи с равными приоритетами, чтобы они возвращались в порядке их первоначального добавления?
• Сравнение кортежей нарушается для пар (приоритет, задача), если приоритеты равны, а задачи не имеют порядка сравнения по умолчанию.
• Если приоритет задачи меняется, как её переместить в новое положение в куче?
• Или если нужно удалить ожидающую задачу, как её найти и удалить из очереди?

Решение первых двух проблем заключается в хранении записей как 3-элементного списка, содержащего приоритет, счётчик записи и задачу. Счётчик записей служит критерием для задач с одинаковым приоритетом, чтобы они возвращались в порядке их добавления. Поскольку ни два счётчика записей не совпадают, сравнение кортежей никогда не будет пытаться непосредственно сравнивать две задачи.

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

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

Остальные проблемы связаны с поиском ожидающей задачи и внесением изменений в её приоритет или полным удалением. Поиск задачи можно осуществить с помощью словаря, указывающего на запись в очереди.

Удаление записи или изменение её приоритета сложнее, потому что это нарушит инварианты структуры кучи. Таким образом, возможным решением является пометка записи как удалённой и добавление новой записи с изменённым приоритетом:

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

Теория

Кучи — это массивы, для которых a[k] <= a[2*k+1] и a[k] <= a[2*k+2] для всех k, считая элементы с 0. Для сравнения, несуществующие элементы считаются бесконечными. Интересное свойство кучи заключается в том, что a[0] всегда является её наименьшим элементом.

Указанное выше странное свойство предназначено для эффективного представления турнира в памяти. Числа ниже — это k, а не a[k]:

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

На дереве выше каждый элемент k стоит над 2*k+1 и 2*k+2. В обычном бинарном турнире, который мы видим в спорте, каждый элемент является победителем над двумя элементами, над которыми он стоит, и мы можем отследить победителя по дереву, чтобы увидеть всех его соперников. Однако во многих компьютерных приложениях таких турниров нам не нужно отслеживать историю победителя. Для большей эффективности памяти, когда победитель повышается по уровню, мы пытаемся заменить его чем-то другим на более низком уровне, и правило становится таким, что элемент и два элемента, над которыми он стоит, содержат три разных элемента, но верхний элемент «побеждает» над двумя элементами, над которыми он стоит.

Если это свойство кучи соблюдается всегда, индекс 0 очевидно является общим победителем. Самый простой алгоритмический способ его удалить и найти «следующего» победителя — переместить проигравшего (скажем, элемент 30 на диаграмме выше) в позицию 0, а затем просеять этот новый элемент 0 по дереву, меняя значения, пока свойство кучи не восстановится. Это очевидно логарифмическая операция от общего числа элементов в дереве. Перебирая все элементы, вы получите сортировку O(n log n).

Приятная особенность этой сортировки заключается в том, что вы можете эффективно вставлять новые элементы во время сортировки, при условии, что вставленные элементы не «лучше», чем последний извлечённый элемент с индексом 0. Это особенно полезно в контексте моделирования, где дерево содержит все входящие события, а «условие победы» означает наименьшее запланированное время. Когда событие планирует другие события для выполнения, они планируются на будущее, поэтому они могут легко попасть в кучу. Итак, куча — хорошая структура для реализации планировщиков (вот что я использовал для своего MIDI-секвенсора :-).

Различные структуры для реализации планировщиков были тщательно изучены, и кучи хороши для этого, так как они достаточно быстрые, скорость почти постоянная, а наихудший случай не сильно отличается от среднего случая. Однако существуют и другие представления, которые в целом более эффективны, но наихудшие случаи могут быть ужасными.

Кучи также очень полезны при больших сортировках на диске. Вы, скорее всего, все знаете, что большая сортировка подразумевает создание «блоков» (которые являются предварительно отсортированными последовательностями, размер которых обычно связан с объёмом оперативной памяти), за которым следуют проходы слияния для этих блоков, причём слияние часто организовано очень хитро 1. Очень важно, чтобы начальная сортировка создавала максимально длинные блоки. Турниры — хороший способ добиться этого. Если, используя всю доступную память для размещения турнира, вы заменяете и просеиваете элементы, которые подходят для текущего блока, вы получите блоки, которые в два раза больше памяти для случайного входного набора, и намного лучше для входных данных, упорядоченных неточно.

Более того, если вы выведете элемент с индексом 0 на диск, и получите входной набор, который может не поместиться в текущем турнире (потому что его значение «побеждает» над последним выведенным значением), то он не сможет поместиться в кучу, поэтому размер кучи уменьшается. Освободившаяся память может быть умно использована немедленно для поэтапного создания второй кучи, которая растёт ровно с той же скоростью, с которой первая куча уменьшается. Когда первая куча полностью исчезает, вы переключаетесь на кучи и начинаете новый блок. Умная и довольно эффективная стратегия!

Короче говоря, кучи — полезные структуры данных, которые стоит знать. Я использую их в нескольких приложениях, и я думаю, что полезно иметь «модуль кучи». :-)

Примечания

1

Современные алгоритмы балансировки дисков более раздражающие, чем умные, и это следствие возможностей поиска дисков. На устройствах, которые не могут искать, таких как большие ленточные накопители, история была совершенно другой, и нужно было быть очень умным, чтобы гарантировать (задолго до этого), что каждое перемещение ленты будет максимально эффективным (то есть наилучшим образом «прогрессирует» слияние). Некоторые ленты даже могли читать назад, и это тоже использовалось для избегания времени перемотки. Поверьте мне, очень хорошие сортировки на лентах были довольно зрелищным зрелищем! На протяжении всех времен сортировка всегда была Великим Искусством! :-)