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

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

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

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

priority queue обычно используется для кучи, и это создает несколько проблем при реализации:

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

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

• Если приоритет задачи меняется, как вы перемещаете ее на новое место в куче

• Или, если необходимо удалить отложенную задачу, как вы можете найти ее и удалить из очереди

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

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

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

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

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

Сноски