heapq — Алгоритм очереди кучи

Исходный код: Lib/heapq.py

Этот модуль предоставляет реализацию алгоритма очереди кучи, также известного как алгоритм очереди с приоритетом.

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

API ниже отличается от учебных алгоритмов кучи по двум аспектам: (a) Мы используем индексацию с нуля. Это делает связь между индексом узла и индексами его дочерних узлов несколько менее очевидной, но лучше подходит, так как Python использует индексацию с нуля. (b) Наш метод pop возвращает наименьший элемент, а не наибольший (в учебниках называется «минимальной кучей»; «максимальная куча» чаще встречается в текстах из-за её пригодности для сортировки на месте).

Эти два аспекта позволяют рассматривать кучу как обычный список Python без неожиданностей: heap[0] — это наименьший элемент, и heap.sort() поддерживает инвариант кучи!

Для создания кучи используйте список, инициализированный [], или можно преобразовать заполненный список в кучу с помощью функции heapify().

Предоставляются следующие функции:

heapq.heappush(heap, item): Добавляет значение item в кучу, сохраняя инвариант кучи.

heapq.heappop(heap): Извлекает и возвращает наименьший элемент из кучи, сохраняя инвариант кучи. Если куча пуста, возникает IndexError. Для доступа к наименьшему элементу без его извлечения используйте heap[0].

heapq.heappushpop(heap, item): Добавляет item в кучу, затем извлекает и возвращает наименьший элемент из кучи. Совместное действие выполняется более эффективно, чем heappush(), за которым следует отдельный вызов heappop().

heapq.heapify(x): Преобразует список x в кучу на месте за линейное время.

heapq.heapreplace(heap, item)

Извлекает и возвращает наименьший элемент из кучи, а также добавляет новый item. Размер кучи не меняется. Если куча пуста, возникает IndexError.

Эта одношаговая операция более эффективна, чем heappop(), за которым следует heappush(), и может быть более уместной при использовании кучи фиксированного размера. Комбинация pop/push всегда возвращает элемент из кучи и заменяет его на item.

Возвращаемое значение может быть больше, чем добавленный item. Если это нежелательно, рассмотрите использование heappushpop() вместо этого. Его комбинация push/pop возвращает меньшее из двух значений, оставляя большее значение в куче.

Модуль также предлагает три общих функции, основанные на кучах.

heapq.merge(*iterables, key=None, reverse=False)

Объединяет несколько отсортированных входных данных в один отсортированный выход (например, объединяет записи с отметками времени из нескольких файлов логов). Возвращает итератор по отсортированным значениям.

Аналогично sorted(itertools.chain(*iterables)) но возвращает итерабельный объект, не загружает все данные в память сразу и предполагает, что каждый из входных потоков уже отсортирован (от меньшего к большему).

Имеет два необязательных аргумента, которые должны быть указаны в качестве ключевых аргументов.

key указывает функцию ключа одного аргумента, которая используется для извлечения ключа сравнения из каждого элемента входных данных. Значение по умолчанию — None (сравнивать элементы напрямую).

reverse — логическое значение. Если установить в True, то входные элементы объединяются так, как будто каждое сравнение было обращено.

Изменено в версии 3.5: Добавлены необязательные параметры key и reverse.

heapq.nlargest(n, iterable, key=None): Возвращает список с n наибольшими элементами из набора данных, определённого iterable. key, если указан, определяет функцию одного аргумента, которая используется для извлечения ключа сравнения из каждого элемента в iterable (например, key=str.lower). Эквивалентно: sorted(iterable, key=key, reverse=True)[:n].

heapq.nsmallest(n, iterable, key=None): Возвращает список с n наименьшими элементами из набора данных, определённого iterable. key, если указан, определяет функцию одного аргумента, которая используется для извлечения ключа сравнения из каждого элемента в iterable (например, key=str.lower). Эквивалентно: sorted(iterable, key=key)[:n].

Две последние функции работают лучше для меньших значений n. Для больших значений более эффективной является функция sorted(). Также, когда n==1, более эффективными являются встроенные функции min() и max(). Если требуется многократное использование этих функций, рассмотрите возможность преобразования итерабельного объекта в фактическую кучу.

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

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

>>> 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.5.2. Примечания по реализации очереди с приоритетом

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

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

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

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

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

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

8.5.3. Теория

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

END_OF_DOCUMENT_MARKER

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

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

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

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

Примечания

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