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

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

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

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

API ниже отличается от учебных алгоритмов кучи в двух аспектах: (а) Мы используем индексацию с нуля. Это делает связь между индексом узла и индексами его дочерних узлов несколько менее очевидной, но более подходит, так как Python использует индексацию с нуля. (б) Наш метод 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)

Извлечь и вернуть наименьший элемент из кучи, а также добавить новый элемент. Размер кучи не изменяется. Если куча пуста, возникает 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, если предоставлен, задаёт функцию с одним аргументом, используемую для извлечения ключа сравнения из каждого элемента в итерируемом объекте: key=str.lower Эквивалентно: sorted(iterable, key=key, reverse=True)[:n]

heapq.nsmallest(n, iterable, key=None)

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

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

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

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

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

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

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

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

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

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

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-секвенсора :-).

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

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

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

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

Примечания