heapq.md
1> **Источник:** https://python-all.ru/3.12/library/heapq.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# `heapq` – алгоритм очереди с кучей89**Исходный код:** [Lib/heapq.py](https://python-all.ru/src/3.12/Lib/heapq.py)1011---1213Этот модуль реализует алгоритм очереди с кучей, также известный как алгоритм приоритетной очереди.1415Кучи (heaps) – это бинарные деревья, в которых каждый родительский узел имеет значение меньшее или равное значениям всех его потомков. Это свойство называется инвариантом кучи.1617В этой реализации используются массивы, для которых `heap[k] <= heap[2*k+1]` и `heap[k] <= heap[2*k+2]` для всех *k*, а нумерация элементов начинается с нуля. Для сравнения несуществующие элементы считаются бесконечными. Интересное свойство кучи: её наименьший элемент всегда находится в корне, `heap[0]`.1819Приведённый ниже API отличается от классических алгоритмов работы с кучами в двух аспектах: (a) используется индексация с нуля. Это делает связь между индексом узла и индексами его потомков чуть менее очевидной, но более подходящей, поскольку Python использует индексацию с нуля. (b) Метод pop возвращает наименьший элемент, а не наибольший (в учебниках это называется «min heap»; «max heap» чаще встречается в литературе из-за его пригодности для сортировки на месте).2021Эти два факта позволяют рассматривать кучу как обычный список Python без неожиданностей: `heap[0]` – это наименьший элемент, а `heap.sort()` поддерживает инвариант кучи!2223Чтобы создать кучу, используйте список, инициализированный значением `[]`, или преобразуйте уже заполненный список в кучу с помощью функции [`heapify()`](https://python-all.ru/3.12/library/heapq.html#heapq.heapify).2425Предоставляются следующие функции:2627#### `heapq.heappush(heap, item)`2829Помещает значение *item* в *heap*, сохраняя инвариант кучи.3031#### `heapq.heappop(heap)`3233Извлекает и возвращает наименьший элемент из *heap*, сохраняя инвариант кучи. Если куча пуста, возбуждается [`IndexError`](https://python-all.ru/3.12/library/exceptions.html#IndexError). Чтобы получить наименьший элемент без извлечения, используйте `heap[0]`.3435#### `heapq.heappushpop(heap, item)`3637Помещает *item* в кучу, затем извлекает и возвращает наименьший элемент из *кучи*. Совместное действие выполняется эффективнее, чем [`heappush()`](https://python-all.ru/3.12/library/heapq.html#heapq.heappush) с последующим отдельным вызовом [`heappop()`](https://python-all.ru/3.12/library/heapq.html#heapq.heappop).3839#### `heapq.heapify(x)`4041Преобразует список *x* в кучу на месте за линейное время.4243#### `heapq.heapreplace(heap, item)`4445Извлекает и возвращает наименьший элемент из *кучи*, а также помещает новый *item*. Размер кучи не меняется. Если куча пуста, возбуждается [`IndexError`](https://python-all.ru/3.12/library/exceptions.html#IndexError).4647Эта одношаговая операция эффективнее, чем [`heappop()`](https://python-all.ru/3.12/library/heapq.html#heapq.heappop) с последующим [`heappush()`](https://python-all.ru/3.12/library/heapq.html#heapq.heappush), и может быть более подходящей при использовании кучи фиксированного размера. Комбинация извлечения/добавления всегда возвращает элемент из кучи и заменяет его на *item*.4849Возвращаемое значение может быть больше, чем добавленный *item*. Если это нежелательно, рассмотрите использование [`heappushpop()`](https://python-all.ru/3.12/library/heapq.html#heapq.heappushpop) вместо него. Его комбинация добавления/извлечения возвращает меньшее из двух значений, оставляя большее в куче.5051Модуль также предоставляет три универсальные функции на основе куч.5253#### `heapq.merge(*iterables, key=None, reverse=False)`5455Сливает несколько отсортированных входных последовательностей в одну отсортированную выходную (например, объединяет записи с временными метками из нескольких файлов журналов). Возвращает [итератор](https://python-all.ru/3.12/glossary.html#term-iterator) по отсортированным значениям.5657Аналогично `sorted(itertools.chain(*iterables))`, но возвращает итерируемый объект, не загружает все данные в память сразу и предполагает, что каждый входной поток уже отсортирован (от наименьшего к наибольшему).5859Имеет два необязательных аргумента, которые должны быть указаны как именованные.6061Параметр *key* задаёт [ключевую функцию](https://python-all.ru/3.12/glossary.html#term-key-function) с одним аргументом, которая используется для извлечения ключа сравнения из каждого входного элемента. Значение по умолчанию – `None` (сравнивать элементы напрямую).6263Параметр *reverse* – логическое значение. Если установлено в `True`, то входные элементы сливаются так, как если бы каждое сравнение было обратным. Для достижения поведения, аналогичного `sorted(itertools.chain(*iterables), reverse=True)`, все итерируемые объекты должны быть отсортированы от наибольшего к наименьшему.6465Изменено в версии 3.5: Добавлены необязательные параметры *key* и *reverse*.6667#### `heapq.nlargest(n, iterable, key=None)`6869Возвращает список из *n* наибольших элементов из набора данных, определённого *iterable*. Если указан *key*, он задаёт функцию с одним аргументом, которая используется для извлечения ключа сравнения из каждого элемента *iterable* (например, `key=str.lower`). Эквивалентно: `sorted(iterable, key=key, reverse=True)[:n]`.7071#### `heapq.nsmallest(n, iterable, key=None)`7273Возвращает список из *n* наименьших элементов из набора данных, определённого *iterable*. Если указан *key*, он задаёт функцию с одним аргументом, которая используется для извлечения ключа сравнения из каждого элемента *iterable* (например, `key=str.lower`). Эквивалентно: `sorted(iterable, key=key)[:n]`.7475Последние две функции лучше всего работают для небольших значений *n*. Для больших значений эффективнее использовать функцию [`sorted()`](https://python-all.ru/3.12/library/functions.html#sorted). Кроме того, когда `n==1`, эффективнее использовать встроенные функции [`min()`](https://python-all.ru/3.12/library/functions.html#min) и [`max()`](https://python-all.ru/3.12/library/functions.html#max). Если эти функции требуются многократно, стоит преобразовать итерируемый объект в настоящую кучу.7677## Простые примеры7879Кучную сортировку ([heapsort](https://python-all.ru/3.12/library/heapq.html)) можно реализовать, помещая все значения в кучу, а затем извлекая наименьшие значения одно за другим:8081```python82>>> def heapsort(iterable):83... h = []84... for value in iterable:85... heappush(h, value)86... return [heappop(h) for i in range(len(h))]87...88>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])89[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]90```9192Это похоже на `sorted(iterable)`, но, в отличие от [`sorted()`](https://python-all.ru/3.12/library/functions.html#sorted), данная реализация не является устойчивой.9394Элементами кучи могут быть кортежи. Это удобно для присвоения значений сравнения (например, приоритетов задач) вместе с основной отслеживаемой записью:9596```python97>>> h = []98>>> heappush(h, (5, 'write code'))99>>> heappush(h, (7, 'release product'))100>>> heappush(h, (1, 'write spec'))101>>> heappush(h, (3, 'create tests'))102>>> heappop(h)103(1, 'write spec')104```105106## Замечания по реализации очереди с приоритетом107108[Очередь с приоритетом](https://python-all.ru/3.12/library/heapq.html) – распространённое применение кучи, и она ставит несколько задач при реализации:109110- Устойчивость сортировки: как добиться, чтобы две задачи с одинаковыми приоритетами возвращались в порядке их добавления?111- Сравнение кортежей нарушается для пар (приоритет, задача), если приоритеты равны, а задачи не имеют порядка сравнения по умолчанию.112- Если приоритет задачи изменился, как переместить её на новую позицию в куче?113- Или если ожидающую задачу нужно удалить, как найти её и убрать из очереди?114115Решение первых двух задач – хранить записи в виде списка из трёх элементов: приоритет, счётчик записей и задача. Счётчик записей служит разрешителем равенства, так что две задачи с одинаковым приоритетом возвращаются в порядке их добавления. А поскольку все счётчики записей различны, сравнение кортежей никогда не попытается сравнивать задачи напрямую.116117Ещё одно решение проблемы несравнимых задач – создать класс-обёртку, который игнорирует элемент задачи и сравнивает только поле приоритета:118119```python120from dataclasses import dataclass, field121from typing import Any122123@dataclass(order=True)124class PrioritizedItem:125 priority: int126 item: Any=field(compare=False)127```128129Остальные трудности связаны с поиском ожидающей задачи и изменением её приоритета или полным удалением. Задачу можно найти с помощью словаря, указывающего на запись в очереди.130131Удаление записи или изменение её приоритета сложнее, так как это нарушит инварианты структуры кучи. Поэтому возможное решение – пометить запись как удалённую и добавить новую запись с изменённым приоритетом:132133```python134pq = [] # список записей, организованных в виде кучи135entry_finder = {} # отображение задач на записи136REMOVED = '<removed-task>' # заполнитель для удалённой задачи137counter = itertools.count() # уникальный счётчик последовательности138139def add_task(task, priority=0):140 'Add a new task or update the priority of an existing task'141 if task in entry_finder:142 remove_task(task)143 count = next(counter)144 entry = [priority, count, task]145 entry_finder[task] = entry146 heappush(pq, entry)147148def remove_task(task):149 'Mark an existing task as REMOVED. Raise KeyError if not found.'150 entry = entry_finder.pop(task)151 entry[-1] = REMOVED152153def pop_task():154 'Remove and return the lowest priority task. Raise KeyError if empty.'155 while pq:156 priority, count, task = heappop(pq)157 if task is not REMOVED:158 del entry_finder[task]159 return task160 raise KeyError('pop from an empty priority queue')161```162163## Теория164165Кучи – это массивы, для которых `a[k] <= a[2*k+1]` и `a[k] <= a[2*k+2]` для всех *k*, где отсчёт элементов ведётся от 0. Для сравнения несуществующие элементы считаются бесконечными. Интересное свойство кучи: `a[0]` всегда является её наименьшим элементом.166167Странный инвариант выше предназначен для эффективного представления турнира в памяти. Числа ниже – это *k*, а не `a[k]`:168169```python170 0171172 1 2173174 3 4 5 6175176 7 8 9 10 11 12 13 1417717815 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30179```180181В дереве выше каждая ячейка *k* стоит над `2*k+1` и `2*k+2`. В обычном бинарном турнире, знакомом нам по спорту, каждая ячейка является победителем над двумя ячейками под ней, и можно проследить путь победителя вниз по дереву, чтобы увидеть всех его соперников. Однако во многих компьютерных применениях таких турниров нам не нужно хранить историю победителя. Чтобы сэкономить память, когда победитель продвигается вверх, мы пытаемся заменить его чем-то другим на более низком уровне, и правило становится таким: ячейка и две стоящие под ней ячейки содержат три разных элемента, но верхняя «выигрывает» у двух нижних.182183Если этот инвариант кучи всегда поддерживается, индекс 0, очевидно, является абсолютным победителем. Простейший алгоритмический способ удалить его и найти «следующего» победителя – переместить какого-нибудь проигравшего (скажем, ячейку 30 на диаграмме выше) на позицию 0, а затем просеивать этот новый 0 вниз по дереву, обменивая значения, пока инвариант не восстановится. Это, очевидно, логарифмическая операция от общего числа элементов в дереве. Перебирая все элементы, получим сортировку за *O*(*n* log *n*).184185Приятная особенность такой сортировки: можно эффективно вставлять новые элементы во время её выполнения, при условии, что вставляемые элементы не «лучше» последнего извлечённого нулевого элемента. Это особенно полезно в сценариях моделирования, где дерево содержит все поступающие события, а условие «выигрыша» означает наименьшее запланированное время. Когда событие планирует выполнение других событий, они планируются на будущее, поэтому легко помещаются в кучу. Таким образом, куча – хорошая структура для реализации планировщиков (именно это я использовал в своём MIDI-секвенсоре :-)).186187Различные структуры для реализации планировщиков были тщательно изучены, и кучи для этого хороши: они достаточно быстры, скорость почти постоянна, и наихудший случай мало отличается от среднего. Однако существуют и другие представления, которые в целом более эффективны, хотя наихудшие случаи могут быть ужасными.188189Кучи также очень полезны при большой сортировке на диске. Вы, вероятно, знаете, что большая сортировка подразумевает создание «серий» (предварительно отсортированных последовательностей, размер которых обычно связан с объёмом оперативной памяти), за которыми следуют проходы слияния этих серий, причём слияние часто очень хитро организовано [\[1\]](https://python-all.ru/3.12/library/heapq.html#id2). Очень важно, чтобы начальная сортировка давала максимально длинные серии. Турниры – хороший способ этого добиться. Если, используя всю доступную память для хранения турнира, заменять и просеивать элементы, которые подходят для текущей серии, то для случайного входа получатся серии вдвое большего размера, чем память, а для частично упорядоченного входа – ещё лучше.190191Более того, если вы выводите нулевой элемент на диск и получаете входное значение, которое не помещается в текущий турнир (потому что оно «выигрывает» у последнего выведенного значения), то оно не может поместиться в кучу, и размер кучи уменьшается. Освободившуюся память можно сразу с умом использовать для постепенного построения второй кучи, которая растёт ровно с той же скоростью, с какой тает первая. Когда первая куча полностью исчезает, вы переключаетесь на вторую и начинаете новую серию. Умно и весьма эффективно!192193Одним словом, кучи – полезные структуры данных, которые стоит знать. Я использую их в нескольких приложениях и считаю, что полезно иметь модуль «heap» под рукой. :-)194195Сноски196197\[[1](https://python-all.ru/3.12/library/heapq.html#id1)\]198199Современные алгоритмы балансировки дисков раздражают больше, чем впечатляют, и это следствие возможностей позиционирования дисков. На устройствах без произвольного доступа, таких как большие ленточные накопители, ситуация была совсем иной, и приходилось проявлять большую изобретательность, чтобы заранее гарантировать, что каждое перемещение ленты будет максимально эффективным (то есть наилучшим образом способствует «продвижению» слияния). Некоторые ленты умели даже читать в обратном направлении, и это использовали, чтобы избежать перемотки. Поверьте, по-настоящему хорошие ленточные сортировки были впечатляющим зрелищем! Во все времена сортировка была Великим Искусством! :-)200