Документация Python неофициальный перевод
Содержание страницы

heapq – алгоритм очереди с кучейheapq – Heap queue algorithm

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

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

Минимальные кучи – это бинарные деревья, в которых каждый родительский узел имеет значение, меньшее или равное любому из своих потомков. Это условие называется инвариантом кучи.

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

Максимальные кучи удовлетворяют обратному инварианту: каждый родительский узел имеет значение больше любого из своих потомков. Они реализованы как списки, для которых maxheap[2*k+1] <= maxheap[k] и maxheap[2*k+2] <= maxheap[k] для всех k, для которых существуют сравниваемые элементы. Корень, maxheap[0], содержит наибольший элемент; heap.sort(reverse=True) поддерживает инвариант максимальной кучи.

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

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

Как и list.sort(), эта реализация использует только оператор < для сравнения как для минимальных, так и для максимальных куч.

В приведённом ниже API и в этой документации термин куча без уточнения обычно обозначает минимальную кучу. API для максимальных куч именуется с использованием суффикса _max.

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

Для минимальных куч предоставляются следующие функции:

heapq.heapify(x)

Преобразует список x в минимальную кучу на месте за линейное время.

heapq.heappush(heap, item)

Помещает значение item в кучу, сохраняя инвариант минимальной кучи.

heapq.heappop(heap)

Извлекает и возвращает наименьший элемент из кучи, сохраняя инвариант минимальной кучи. Если куча пуста, возбуждается IndexError. Чтобы получить наименьший элемент без извлечения, используйте heap[0].

heapq.heappushpop(heap, item)

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

heapq.heapreplace(heap, item)

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

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

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

Для максимальных куч предоставляются следующие функции:

heapq.heapify_max(x)

Преобразует список x в максимальную кучу на месте за линейное время.

Добавлено в версии 3.14.

heapq.heappush_max(heap, item)

Помещает значение item в максимальную кучу heap, сохраняя инвариант максимальной кучи.

Добавлено в версии 3.14.

heapq.heappop_max(heap)

Извлекает и возвращает наибольший элемент из максимальной кучи heap, сохраняя инвариант максимальной кучи. Если максимальная куча пуста, возбуждается IndexError. Чтобы получить наибольший элемент без извлечения, используйте maxheap[0].

Добавлено в версии 3.14.

heapq.heappushpop_max(heap, item)

Добавляет элемент item в max-кучу heap, затем извлекает и возвращает наибольший элемент из heap. Совместная операция выполняется эффективнее, чем heappush_max() с последующим отдельным вызовом heappop_max().

Добавлено в версии 3.14.

heapq.heapreplace_max(heap, item)

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

Возвращаемое значение может быть меньше добавленного элемента item. За подробными указаниями по использованию обращайтесь к аналогичной функции heapreplace().

Добавлено в версии 3.14.

Модуль также предоставляет три универсальные функции на основе куч.

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(). Если эти функции требуются многократно, стоит преобразовать итерируемый объект в настоящую кучу.

Простые примеры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')

Другие примененияOther Applications

Медианы – это мера центральной тенденции для набора чисел. В распределениях, искажённых выбросами, медиана даёт более устойчивую оценку, чем среднее (арифметическое среднее). Скользящая медиана – это онлайн-алгоритм, который непрерывно обновляется по мере поступления новых данных.

Скользящую медиану можно эффективно реализовать, балансируя две кучи: max-кучу для значений на уровне средней точки или ниже, и min-кучу для значений выше средней точки. Когда обе кучи имеют одинаковый размер, новая медиана равна среднему значению вершин двух куч; в противном случае медиана находится на вершине большей кучи:

def running_median(iterable):
    "Yields the cumulative median of values seen so far."

    lo = []  # максимальная куча
    hi = []  # минимальная куча (того же размера или на один меньше, чем lo)

    for x in iterable:
        if len(lo) == len(hi):
            heappush_max(lo, heappushpop(hi, x))
            yield lo[0]
        else:
            heappush(hi, heappushpop_max(lo, x))
            yield (lo[0] + hi[0]) / 2

Например:

>>> list(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0]))
[5.0, 7.0, 5.0, 7.0, 8.0, 8.5]

Замечания по реализации очереди с приоритетомPriority Queue Implementation Notes

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

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

  • Сравнение кортежей нарушается для пар (приоритет, задача), если приоритеты равны, а задачи не имеют порядка сравнения по умолчанию.

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

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

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

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

from dataclasses import dataclass, field
from typing import Any

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

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

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

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

ТеорияTheory

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

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

Пример двоичного дерева (min-куча).

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

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

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

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

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

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

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

Сноски