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


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

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

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

Аналогична 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('выталкивается из пустой очереди с приоритетом')

Теория

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

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

Сноски

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