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

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

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

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

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

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

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

Предусмотрены следующие функции:

heapq.heappush(heap, item)

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

heapq.heappop(heap)

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

heapq.heappushpop(heap, item)

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

heapq.heapify(x)

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

heapq.heapreplace(heap, item)

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

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

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

Примечания по реализации очереди приоритетов

Приоритетная очередь - общее использование для кучи, и это представляет несколько проблем реализации:

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

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

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

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):
    'Добавить новую задачу или обновить приоритет существующей задачи'
    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):
    'Отметить существующее задание как REMOVED. Поднять KeyError, если не найден.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Удалить и вернуть задачу с самым низким приоритетом. Поднять KeyError, если пусто.'
    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 секвенсора :-).

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

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

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

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

Сноски

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