8.4. heapq – Алгоритм очереди с кучей¶heapq – Heap queue algorithm

8.4.1. Основные примеры¶Basic Examples

Кучную сортировку (heapsort) можно реализовать, помещая все значения в кучу, а затем извлекая наименьшие значения одно за другим:

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

8.4.2. Примечания к реализации очереди с приоритетом¶Priority Queue Implementation Notes

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

• Устойчивость сортировки: как добиться, чтобы две задачи с одинаковыми приоритетами возвращались в порядке их добавления?

• В Python 3 сравнение кортежей для пар (priority, задача) перестаёт работать корректно, если приоритеты равны, а для задач не задан порядок сравнения по умолчанию.

• Если приоритет задачи изменился, как переместить её на новую позицию в куче?

• Или если ожидающую задачу нужно удалить, как найти её и убрать из очереди?

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

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

Удаление записи или изменение её приоритета сложнее, поскольку это нарушит инварианты структуры кучи. Поэтому возможное решение – пометить существующую запись как удалённую и добавить новую запись с изменённым приоритетом:

pq = []                         # список записей, организованных в виде кучи
entry_finder = {}               # отображение задач на записи
REMOVED = '<removed-task>'      # заполнитель для удалённой задачи
counter = itertools.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')

8.4.3. Теория¶Theory

Кучи – это массивы, для которых 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).

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

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

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

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

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

Сноски

1

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