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

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

Сортировка методом кучи можно реализовать, добавив все значения в кучу, а затем извлекая наименьшие значения по одному:

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

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

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

Примечания

1

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