Содержание страницы
heapq – алгоритм очереди с приоритетом (куча)¶heapq – Heap queue algorithm
Этот модуль реализует алгоритм очереди с кучей, также известный как алгоритм приоритетной очереди.
Кучи – это массивы, для которых heap[k] <= heap[2*k+1] и heap[k] <= heap[2*k+2] для всех k, при нумерации элементов с нуля. Для сравнения несуществующие элементы считаются бесконечными. Интересное свойство кучи: heap[0] всегда является наименьшим элементом.
Приведённый ниже API отличается от классических алгоритмов работы с кучами в двух аспектах: (a) используется индексация с нуля. Это делает связь между индексом узла и индексами его потомков чуть менее очевидной, но более подходящей, поскольку Python использует индексацию с нуля. (b) Метод pop возвращает наименьший элемент, а не наибольший (в учебниках это называется «min heap»; «max heap» чаще встречается в литературе из-за его пригодности для сортировки на месте).
Эти два свойства позволяют рассматривать кучу как обычный список Python без сюрпризов: heap[0] – наименьший элемент, а heap.sort() сохраняет инвариант кучи!
Чтобы создать кучу, используйте список, инициализированный значением [], или можно преобразовать заполненный список в кучу с помощью функции heapify().
Предоставляются следующие функции:
- heapq.heappush(heap, item)¶
- Помещает значение item в heap, сохраняя инвариант кучи.
- heapq.heappop(heap)¶
- Извлекает и возвращает наименьший элемент из кучи, сохраняя инвариант кучи. Если куча пуста, возникает исключение IndexError.
- heapq.heappushpop(heap, item)¶
- Помещает item в кучу, затем извлекает и возвращает наименьший элемент из heap. Совместное действие выполняется эффективнее, чем heappush() с последующим отдельным вызовом heappop().
- heapq.heapify(x)¶
- Преобразует список x в кучу на месте за линейное время.
- heapq.heapreplace(heap, item)¶
Извлекает и возвращает наименьший элемент из heap, а также помещает новый item. Размер кучи не изменяется. Если куча пуста, возбуждается IndexError. Это более эффективно, чем heappop(), за которым следует heappush(), и может быть более подходящим при использовании кучи фиксированного размера. Обратите внимание, что возвращаемое значение может быть больше, чем item! Это ограничивает разумное использование данной функции, если она не является частью условной замены:
if item > heap[0]: item = heapreplace(heap, item)
Пример использования:
>>> from heapq import heappush, heappop
>>> heap = []
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
>>> for item in data:
... heappush(heap, item)
...
>>> ordered = []
>>> while heap:
... ordered.append(heappop(heap))
...
>>> ordered
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> data.sort()
>>> data == ordered
True
Использование кучи для вставки элементов в нужное место очереди с приоритетом:
>>> heap = []
>>> data = [(1, 'J'), (4, 'N'), (3, 'H'), (2, 'O')]
>>> for item in data:
... heappush(heap, item)
...
>>> while heap:
... print(heappop(heap)[1])
J
O
H
N
Модуль также предоставляет три универсальные функции на основе куч.
- heapq.merge(*iterables)¶
Сливает несколько отсортированных входных последовательностей в одну отсортированную выходную (например, объединяет записи с временными метками из нескольких файлов журналов). Возвращает итератор по отсортированным значениям.
Похож на sorted(itertools.chain(*iterables)), но возвращает итератор, не загружает все данные в память сразу и предполагает, что каждый из входных потоков уже отсортирован (от меньшего к большему).
- heapq.nlargest(n, iterable[, key])¶
- Возвращает список из n наибольших элементов из набора данных, заданного iterable. Если указан key, он задаёт функцию одного аргумента, используемую для извлечения ключа сравнения из каждого элемента итератора: key=str.lower Эквивалентно: sorted(iterable, key=key, reverse=True)[:n]
- heapq.nsmallest(n, iterable[, key])¶
- Возвращает список из n наименьших элементов из набора данных, заданного iterable. Если указан key, он задаёт функцию одного аргумента, используемую для извлечения ключа сравнения из каждого элемента итератора: key=str.lower Эквивалентно: sorted(iterable, key=key)[:n]
Последние две функции наиболее эффективны для небольших значений n. Для больших значений эффективнее использовать функцию sorted(). Кроме того, когда n==1, эффективнее использовать встроенные функции min() и max().
Теория¶Theory
(Это пояснение принадлежит Франсуа Пинару. Код Python для этого модуля был предоставлен Кевином О’Коннором.)
Кучи – это массивы, для которых a[k] <= a[2*k+1] и a[k] <= a[2*k+2] для всех k, считая элементы с нуля. Для сравнения несуществующие элементы считаются бесконечными. Интересное свойство кучи заключается в том, что 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]. Очень важно, чтобы начальная сортировка создавала как можно более длинные прогоны. Турниры – хороший способ для этого. Если, используя всю доступную память для проведения турнира, заменять и просеивать элементы, которые вписываются в текущий прогон, то получаются прогоны, вдвое превышающие размер памяти для случайного ввода, и гораздо лучше для ввода с нечеткой упорядоченностью.
Более того, если вы выводите нулевой элемент на диск и получаете входное значение, которое не помещается в текущий турнир (потому что оно «выигрывает» у последнего выведенного значения), то оно не может поместиться в кучу, и размер кучи уменьшается. Освободившуюся память можно сразу с умом использовать для постепенного построения второй кучи, которая растёт ровно с той же скоростью, с какой тает первая. Когда первая куча полностью исчезает, вы переключаетесь на вторую и начинаете новую серию. Умно и весьма эффективно!
Одним словом, кучи – полезные структуры данных, которые стоит знать. Я использую их в нескольких приложениях и считаю, что полезно иметь модуль «heap» под рукой. :-)
Сноски
| [1] | Современные алгоритмы балансировки дисков раздражают больше, чем впечатляют, и это следствие возможностей позиционирования дисков. На устройствах без произвольного доступа, таких как большие ленточные накопители, ситуация была совсем иной, и приходилось проявлять большую изобретательность, чтобы заранее гарантировать, что каждое перемещение ленты будет максимально эффективным (то есть наилучшим образом способствует «продвижению» слияния). Некоторые ленты умели даже читать в обратном направлении, и это использовали, чтобы избежать перемотки. Поверьте, по-настоящему хорошие ленточные сортировки были впечатляющим зрелищем! Во все времена сортировка была Великим Искусством! :-) |