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 является обычным использованием для кучи, и это создает несколько проблем при реализации:

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

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

• Если приоритет задачи меняется, как переместить ее на новую позицию в куче?

• Или если отложенную задачу нужно удалить, как ее найти и удалить из очереди?

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

Другим решением проблемы несравнимых задач является создание класса-обертки, который игнорирует элемент задачи и сравнивает только поле приоритета:

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

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

Сноски

1

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