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

Новое в версии 2.3.

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

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

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

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

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

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

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

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

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

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

Новое в версии 2.6.

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

heapq.heapreplace(heap, item)

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

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

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

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

heapq.merge(*iterables)

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

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

Новое в версии 2.6.

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

Новое в версии 2.4.

Изменено в версии 2.5: Добавлен необязательный аргумент key.

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

Новое в версии 2.4.

Изменено в версии 2.5: Добавлен необязательный аргумент key.

Последние две функции лучше всего работают для меньших значений 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. Примечания по реализации очереди с приоритетами

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

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

Решение первых двух задач заключается в хранении записей как списков из 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')

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

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

Примечания

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