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

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

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

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

Решение первых двух задач заключается в хранении записей в виде списка из 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]. Очень важно, чтобы начальная сортировка создавала как можно более длинные пробежки. Турниры — хороший способ для этого. Если, используя всю доступную память для турнира, вы замените и просеете элементы, которые подходят для текущей пробежки, вы получите пробежки, которые в два раза больше памяти для случайного ввода, и намного лучше для ввода, в котором порядок задан приблизительно.

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

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

Примечания