heapq.md
1> **Источник:** https://python-all.ru/3.16/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/main/Lib/heapq.py)1011---1213Этот модуль реализует алгоритм очереди с кучей, также известный как алгоритм приоритетной очереди.1415Минимальные кучи – это бинарные деревья, в которых каждый родительский узел имеет значение, меньшее или равное любому из своих потомков. Это условие называется инвариантом кучи.1617Для минимальных куч эта реализация использует списки, для которых `heap[k] <= heap[2*k+1]` и `heap[k] <= heap[2*k+2]` для всех *k*, для которых существуют сравниваемые элементы. Элементы нумеруются с нуля. Интересное свойство минимальной кучи: её наименьший элемент всегда находится в корне, `heap[0]`.1819Максимальные кучи удовлетворяют обратному инварианту: каждый родительский узел имеет значение *больше* любого из своих потомков. Они реализованы как списки, для которых `maxheap[2*k+1] <= maxheap[k]` и `maxheap[2*k+2] <= maxheap[k]` для всех *k*, для которых существуют сравниваемые элементы. Корень, `maxheap[0]`, содержит *наибольший* элемент; `heap.sort(reverse=True)` поддерживает инвариант максимальной кучи.2021API `heapq` отличается от книжных алгоритмов куч по двум аспектам: (a) используется нумерация с нуля. Это делает связь между индексом узла и индексами его потомков чуть менее очевидной, но более подходящей, поскольку Python использует нумерацию с нуля. (b) В учебниках часто делают упор на максимальные кучи из-за их пригодности для сортировки на месте. Наша реализация отдаёт предпочтение минимальным кучам, так как они лучше соответствуют Python [`lists`](https://python-all.ru/3.16/library/stdtypes.html#list).2223Эти два аспекта позволяют рассматривать кучу как обычный список Python без неожиданностей: `heap[0]` – наименьший элемент, а `heap.sort()` поддерживает инвариант кучи!2425Как и [`list.sort()`](https://python-all.ru/3.16/library/stdtypes.html#list.sort), эта реализация использует только оператор `<` для сравнения как для минимальных, так и для максимальных куч.2627В приведённом ниже API и в этой документации термин *куча* без уточнения обычно обозначает минимальную кучу. API для максимальных куч именуется с использованием суффикса `_max`.2829Чтобы создать кучу, используйте список, инициализированный как `[]`, или преобразуйте существующий список в минимальную или максимальную кучу с помощью функций [`heapify()`](https://python-all.ru/3.16/library/heapq.html#heapq.heapify) или [`heapify_max()`](https://python-all.ru/3.16/library/heapq.html#heapq.heapify_max) соответственно.3031Для минимальных куч предоставляются следующие функции:3233#### `heapq.heapify(x)`3435Преобразует список *x* в минимальную кучу на месте за линейное время.3637#### `heapq.heappush(heap, item)`3839Помещает значение *item* в *кучу*, сохраняя инвариант минимальной кучи.4041#### `heapq.heappop(heap)`4243Извлекает и возвращает наименьший элемент из *кучи*, сохраняя инвариант минимальной кучи. Если куча пуста, возбуждается [`IndexError`](https://python-all.ru/3.16/library/exceptions.html#IndexError). Чтобы получить наименьший элемент без извлечения, используйте `heap[0]`.4445#### `heapq.heappushpop(heap, item)`4647Помещает *item* в кучу, затем извлекает и возвращает наименьший элемент из *кучи*. Совместное действие выполняется эффективнее, чем [`heappush()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappush) с последующим отдельным вызовом [`heappop()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappop).4849#### `heapq.heapreplace(heap, item)`5051Извлекает и возвращает наименьший элемент из *кучи*, а также помещает новый *item*. Размер кучи не меняется. Если куча пуста, возбуждается [`IndexError`](https://python-all.ru/3.16/library/exceptions.html#IndexError).5253Эта одношаговая операция эффективнее, чем [`heappop()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappop) с последующим [`heappush()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappush), и может быть более подходящей при использовании кучи фиксированного размера. Комбинация извлечения/добавления всегда возвращает элемент из кучи и заменяет его на *item*.5455Возвращаемое значение может быть больше, чем добавленный *item*. Если это нежелательно, рассмотрите использование [`heappushpop()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappushpop) вместо него. Его комбинация добавления/извлечения возвращает меньшее из двух значений, оставляя большее в куче.5657Для максимальных куч предоставляются следующие функции:5859#### `heapq.heapify_max(x)`6061Преобразует список *x* в максимальную кучу на месте за линейное время.6263Добавлено в версии 3.14.6465#### `heapq.heappush_max(heap, item)`6667Помещает значение *item* в максимальную кучу *heap*, сохраняя инвариант максимальной кучи.6869Добавлено в версии 3.14.7071#### `heapq.heappop_max(heap)`7273Извлекает и возвращает наибольший элемент из максимальной кучи *heap*, сохраняя инвариант максимальной кучи. Если максимальная куча пуста, возбуждается [`IndexError`](https://python-all.ru/3.16/library/exceptions.html#IndexError). Чтобы получить наибольший элемент без извлечения, используйте `maxheap[0]`.7475Добавлено в версии 3.14.7677#### `heapq.heappushpop_max(heap, item)`7879Добавляет элемент *item* в max-кучу *heap*, затем извлекает и возвращает наибольший элемент из *heap*. Совместная операция выполняется эффективнее, чем [`heappush_max()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappush_max) с последующим отдельным вызовом [`heappop_max()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappop_max).8081Добавлено в версии 3.14.8283#### `heapq.heapreplace_max(heap, item)`8485Извлекает и возвращает наибольший элемент из max-кучи *heap*, а также добавляет новый элемент *item*. Размер max-кучи не изменяется. Если max-куча пуста, возбуждается исключение [`IndexError`](https://python-all.ru/3.16/library/exceptions.html#IndexError).8687Возвращаемое значение может быть меньше добавленного элемента *item*. За подробными указаниями по использованию обращайтесь к аналогичной функции [`heapreplace()`](https://python-all.ru/3.16/library/heapq.html#heapq.heapreplace).8889Добавлено в версии 3.14.9091Модуль также предоставляет три универсальные функции на основе куч.9293#### `heapq.merge(*iterables, key=None, reverse=False)`9495Сливает несколько отсортированных входных последовательностей в одну отсортированную выходную (например, объединяет записи с временными метками из нескольких файлов журналов). Возвращает [итератор](https://python-all.ru/3.16/glossary.html#term-iterator) по отсортированным значениям.9697Аналогично `sorted(itertools.chain(*iterables))`, но возвращает итерируемый объект, не загружает все данные в память сразу и предполагает, что каждый входной поток уже отсортирован (от наименьшего к наибольшему).9899Имеет два необязательных аргумента, которые должны быть указаны как именованные.100101Параметр *key* задаёт [ключевую функцию](https://python-all.ru/3.16/glossary.html#term-key-function) с одним аргументом, которая используется для извлечения ключа сравнения из каждого входного элемента. Значение по умолчанию – `None` (сравнивать элементы напрямую).102103Параметр *reverse* – логическое значение. Если установлено в `True`, то входные элементы сливаются так, как если бы каждое сравнение было обратным. Для достижения поведения, аналогичного `sorted(itertools.chain(*iterables), reverse=True)`, все итерируемые объекты должны быть отсортированы от наибольшего к наименьшему.104105Изменено в версии 3.5: Добавлены необязательные параметры *key* и *reverse*.106107#### `heapq.nlargest(n, iterable, key=None)`108109Возвращает список из *n* наибольших элементов из набора данных, определённого *iterable*. Если указан *key*, он задаёт функцию с одним аргументом, которая используется для извлечения ключа сравнения из каждого элемента *iterable* (например, `key=str.lower`). Эквивалентно: `sorted(iterable, key=key, reverse=True)[:n]`.110111#### `heapq.nsmallest(n, iterable, key=None)`112113Возвращает список из *n* наименьших элементов из набора данных, определённого *iterable*. Если указан *key*, он задаёт функцию с одним аргументом, которая используется для извлечения ключа сравнения из каждого элемента *iterable* (например, `key=str.lower`). Эквивалентно: `sorted(iterable, key=key)[:n]`.114115Последние две функции лучше всего работают для небольших значений *n*. Для больших значений эффективнее использовать функцию [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted). Кроме того, когда `n==1`, эффективнее использовать встроенные функции [`min()`](https://python-all.ru/3.16/library/functions.html#min) и [`max()`](https://python-all.ru/3.16/library/functions.html#max). Если эти функции требуются многократно, стоит преобразовать итерируемый объект в настоящую кучу.116117## Простые примеры118119Кучную сортировку ([heapsort](https://python-all.ru/3.16/library/heapq.html)) можно реализовать, помещая все значения в кучу, а затем извлекая наименьшие значения одно за другим:120121```python122>>> def heapsort(iterable):123... h = []124... for value in iterable:125... heappush(h, value)126... return [heappop(h) for i in range(len(h))]127...128>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])129[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]130```131132Это похоже на `sorted(iterable)`, но, в отличие от [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted), данная реализация не является устойчивой.133134Элементами кучи могут быть кортежи. Это удобно для присвоения значений сравнения (например, приоритетов задач) вместе с основной отслеживаемой записью:135136```python137>>> h = []138>>> heappush(h, (5, 'write code'))139>>> heappush(h, (7, 'release product'))140>>> heappush(h, (1, 'write spec'))141>>> heappush(h, (3, 'create tests'))142>>> heappop(h)143(1, 'write spec')144```145146## Другие применения147148[Медианы](https://python-all.ru/3.16/library/heapq.html) – это мера центральной тенденции для набора чисел. В распределениях, искажённых выбросами, медиана даёт более устойчивую оценку, чем среднее (арифметическое среднее). Скользящая медиана – это [онлайн-алгоритм](https://python-all.ru/3.16/library/heapq.html), который непрерывно обновляется по мере поступления новых данных.149150Скользящую медиану можно эффективно реализовать, балансируя две кучи: max-кучу для значений на уровне средней точки или ниже, и min-кучу для значений выше средней точки. Когда обе кучи имеют одинаковый размер, новая медиана равна среднему значению вершин двух куч; в противном случае медиана находится на вершине большей кучи:151152```python153def running_median(iterable):154 "Yields the cumulative median of values seen so far."155156 lo = [] # максимальная куча157 hi = [] # минимальная куча (того же размера или на один меньше, чем lo)158159 for x in iterable:160 if len(lo) == len(hi):161 heappush_max(lo, heappushpop(hi, x))162 yield lo[0]163 else:164 heappush(hi, heappushpop_max(lo, x))165 yield (lo[0] + hi[0]) / 2166```167168Например:169170```python171>>> list(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0]))172[5.0, 7.0, 5.0, 7.0, 8.0, 8.5]173```174175## Замечания по реализации очереди с приоритетом176177[Очередь с приоритетом](https://python-all.ru/3.16/library/heapq.html) – распространённое применение кучи, и она ставит несколько задач при реализации:178179- Устойчивость сортировки: как добиться, чтобы две задачи с одинаковыми приоритетами возвращались в порядке их добавления?180- Сравнение кортежей нарушается для пар (приоритет, задача), если приоритеты равны, а задачи не имеют порядка сравнения по умолчанию.181- Если приоритет задачи изменился, как переместить её на новую позицию в куче?182- Или если ожидающую задачу нужно удалить, как найти её и убрать из очереди?183184Решение первых двух задач – хранить записи в виде списка из трёх элементов: приоритет, счётчик записей и задача. Счётчик записей служит разрешителем равенства, так что две задачи с одинаковым приоритетом возвращаются в порядке их добавления. А поскольку все счётчики записей различны, сравнение кортежей никогда не попытается сравнивать задачи напрямую.185186Ещё одно решение проблемы несравнимых задач – создать класс-обёртку, который игнорирует элемент задачи и сравнивает только поле приоритета:187188```python189from dataclasses import dataclass, field190from typing import Any191192@dataclass(order=True)193class PrioritizedItem:194 priority: int195 item: Any=field(compare=False)196```197198Остальные трудности связаны с поиском ожидающей задачи и изменением её приоритета или полным удалением. Задачу можно найти с помощью словаря, указывающего на запись в очереди.199200Удаление записи или изменение её приоритета сложнее, так как это нарушит инварианты структуры кучи. Поэтому возможное решение – пометить запись как удалённую и добавить новую запись с изменённым приоритетом:201202```python203pq = [] # список записей, организованных в виде кучи204entry_finder = {} # отображение задач на записи205REMOVED = '<removed-task>' # заполнитель для удалённой задачи206counter = itertools.count() # уникальный счётчик последовательности207208def add_task(task, priority=0):209 'Add a new task or update the priority of an existing task'210 if task in entry_finder:211 remove_task(task)212 count = next(counter)213 entry = [priority, count, task]214 entry_finder[task] = entry215 heappush(pq, entry)216217def remove_task(task):218 'Mark an existing task as REMOVED. Raise KeyError if not found.'219 entry = entry_finder.pop(task)220 entry[-1] = REMOVED221222def pop_task():223 'Remove and return the lowest priority task. Raise KeyError if empty.'224 while pq:225 priority, count, task = heappop(pq)226 if task is not REMOVED:227 del entry_finder[task]228 return task229 raise KeyError('pop from an empty priority queue')230```231232## Теория233234Кучи – это массивы, для которых `a[k] <= a[2*k+1]` и `a[k] <= a[2*k+2]` для всех *k*, где отсчёт элементов ведётся от 0. Для сравнения несуществующие элементы считаются бесконечными. Интересное свойство кучи: `a[0]` всегда является её наименьшим элементом.235236Странный инвариант выше предназначен для эффективного представления турнира в памяти. Числа ниже – это *k*, а не `a[k]`:237238239240В дереве выше каждая ячейка *k* стоит над `2*k+1` и `2*k+2`. В обычном бинарном турнире, знакомом нам по спорту, каждая ячейка является победителем над двумя ячейками под ней, и можно проследить путь победителя вниз по дереву, чтобы увидеть всех его соперников. Однако во многих компьютерных применениях таких турниров нам не нужно хранить историю победителя. Чтобы сэкономить память, когда победитель продвигается вверх, мы пытаемся заменить его чем-то другим на более низком уровне, и правило становится таким: ячейка и две стоящие под ней ячейки содержат три разных элемента, но верхняя «выигрывает» у двух нижних.241242Если этот инвариант кучи всегда поддерживается, индекс 0, очевидно, является абсолютным победителем. Простейший алгоритмический способ удалить его и найти «следующего» победителя – переместить какого-нибудь проигравшего (скажем, ячейку 30 на диаграмме выше) на позицию 0, а затем просеивать этот новый 0 вниз по дереву, обменивая значения, пока инвариант не восстановится. Это, очевидно, логарифмическая операция от общего числа элементов в дереве. Перебирая все элементы, получим сортировку за *O*(*n* log *n*).243244Приятная особенность такой сортировки: можно эффективно вставлять новые элементы во время её выполнения, при условии, что вставляемые элементы не «лучше» последнего извлечённого нулевого элемента. Это особенно полезно в сценариях моделирования, где дерево содержит все поступающие события, а условие «выигрыша» означает наименьшее запланированное время. Когда событие планирует выполнение других событий, они планируются на будущее, поэтому легко помещаются в кучу. Таким образом, куча – хорошая структура для реализации планировщиков (именно это я использовал в своём MIDI-секвенсоре :-)).245246Различные структуры для реализации планировщиков были тщательно изучены, и кучи для этого хороши: они достаточно быстры, скорость почти постоянна, и наихудший случай мало отличается от среднего. Однако существуют и другие представления, которые в целом более эффективны, хотя наихудшие случаи могут быть ужасными.247248Кучи также очень полезны при большой сортировке на диске. Вы, вероятно, знаете, что большая сортировка подразумевает создание «серий» (предварительно отсортированных последовательностей, размер которых обычно связан с объёмом оперативной памяти), за которыми следуют проходы слияния этих серий, причём слияние часто очень хитро организовано [\[1\]](https://python-all.ru/3.16/library/heapq.html#id2). Очень важно, чтобы начальная сортировка давала максимально длинные серии. Турниры – хороший способ этого добиться. Если, используя всю доступную память для хранения турнира, заменять и просеивать элементы, которые подходят для текущей серии, то для случайного входа получатся серии вдвое большего размера, чем память, а для частично упорядоченного входа – ещё лучше.249250Более того, если вы выводите нулевой элемент на диск и получаете входное значение, которое не помещается в текущий турнир (потому что оно «выигрывает» у последнего выведенного значения), то оно не может поместиться в кучу, и размер кучи уменьшается. Освободившуюся память можно сразу с умом использовать для постепенного построения второй кучи, которая растёт ровно с той же скоростью, с какой тает первая. Когда первая куча полностью исчезает, вы переключаетесь на вторую и начинаете новую серию. Умно и весьма эффективно!251252Одним словом, кучи – полезные структуры данных, которые стоит знать. Я использую их в нескольких приложениях и считаю, что полезно иметь модуль «heap» под рукой. :-)253254Сноски255256\[[1](https://python-all.ru/3.16/library/heapq.html#id1)\]257258Современные алгоритмы балансировки дисков раздражают больше, чем впечатляют, и это следствие возможностей позиционирования дисков. На устройствах без произвольного доступа, таких как большие ленточные накопители, ситуация была совсем иной, и приходилось проявлять большую изобретательность, чтобы заранее гарантировать, что каждое перемещение ленты будет максимально эффективным (то есть наилучшим образом способствует «продвижению» слияния). Некоторые ленты умели даже читать в обратном направлении, и это использовали, чтобы избежать перемотки. Поверьте, по-настоящему хорошие ленточные сортировки были впечатляющим зрелищем! Во все времена сортировка была Великим Искусством! :-)259