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

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