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)

Извлечь и вернуть наименьший элемент из кучи, а также поместить новый 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, то элементы входных данных объединяются так, как будто каждое сравнение было обращено. Для достижения поведения, аналогичного sorted(itertools.chain(*iterables), 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(). Если требуется многократное использование этих функций, рассмотрите возможность превращения итерируемого объекта в фактическую кучу.

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

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

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

END_OF_DOCUMENT_MARKER

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

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

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

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

Примечания

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