heapq.md
1> **Источник:** https://python-all.ru/3.3/library/heapq.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# 8.5. [`heapq`](https://python-all.ru/3.3/library/heapq.html#module-heapq) – Алгоритм очереди на куче89**Исходный код:** [Lib/heapq.py](https://python-all.ru/src/3.3/Lib/heapq.py)1011---1213Этот модуль реализует алгоритм очереди с кучей, также известный как алгоритм приоритетной очереди.1415Кучи – это бинарные деревья, в которых каждый родительский узел имеет значение меньше или равное любому из его дочерних узлов. В данной реализации используются массивы, для которых `heap[k] <= heap[2*k+1]` и `heap[k] <= heap[2*k+2]` для всех *k*, считая элементы с нуля. Для сравнения несуществующие элементы считаются бесконечными. Интересное свойство кучи – наименьший элемент всегда находится в корне, `heap[0]`.1617Приведённый ниже API отличается от классических алгоритмов работы с кучами в двух аспектах: (a) используется индексация с нуля. Это делает связь между индексом узла и индексами его потомков чуть менее очевидной, но более подходящей, поскольку Python использует индексацию с нуля. (b) Метод pop возвращает наименьший элемент, а не наибольший (в учебниках это называется «min heap»; «max heap» чаще встречается в литературе из-за его пригодности для сортировки на месте).1819Эти два свойства позволяют рассматривать кучу как обычный список Python без сюрпризов: `heap[0]` – наименьший элемент, а `heap.sort()` сохраняет инвариант кучи!2021Чтобы создать кучу, используйте список, инициализированный значением `[]`, или можно преобразовать заполненный список в кучу с помощью функции [`heapify()`](https://python-all.ru/3.3/library/heapq.html#heapq.heapify).2223Предоставляются следующие функции:2425#### `heapq.heappush(heap, item)`2627Помещает значение *item* в *heap*, сохраняя инвариант кучи.2829#### `heapq.heappop(heap)`3031Извлекает и возвращает наименьший элемент из *кучи*, сохраняя инвариант кучи. Если куча пуста, возникает исключение [`IndexError`](https://python-all.ru/3.3/library/exceptions.html#IndexError).3233#### `heapq.heappushpop(heap, item)`3435Помещает *item* в кучу, затем извлекает и возвращает наименьший элемент из *heap*. Совместное действие выполняется эффективнее, чем [`heappush()`](https://python-all.ru/3.3/library/heapq.html#heapq.heappush) с последующим отдельным вызовом [`heappop()`](https://python-all.ru/3.3/library/heapq.html#heapq.heappop).3637#### `heapq.heapify(x)`3839Преобразует список *x* в кучу на месте за линейное время.4041#### `heapq.heapreplace(heap, item)`4243Извлекает и возвращает наименьший элемент из *heap*, а также помещает новый *item*. Размер кучи не меняется. Если куча пуста, вызывается исключение [`IndexError`](https://python-all.ru/3.3/library/exceptions.html#IndexError).4445Эта одношаговая операция эффективнее, чем [`heappop()`](https://python-all.ru/3.3/library/heapq.html#heapq.heappop) с последующим [`heappush()`](https://python-all.ru/3.3/library/heapq.html#heapq.heappush), и может быть более подходящей при использовании кучи фиксированного размера. Комбинация pop/push всегда возвращает элемент из кучи и заменяет его на *item*.4647Возвращаемое значение может быть больше добавленного *item*. Если это нежелательно, рассмотрите использование [`heappushpop()`](https://python-all.ru/3.3/library/heapq.html#heapq.heappushpop). Его комбинация push/pop возвращает меньшее из двух значений, оставляя большее значение в куче.4849Модуль также предоставляет три универсальные функции на основе куч.5051#### `heapq.merge(*iterables)`5253Сливает несколько отсортированных входных последовательностей в одну отсортированную выходную (например, объединяет записи с временными метками из нескольких файлов журналов). Возвращает [*итератор*](https://python-all.ru/3.3/glossary.html#term-iterator) по отсортированным значениям.5455Похож на `sorted(itertools.chain(*iterables))`, но возвращает итератор, не загружает все данные в память сразу и предполагает, что каждый из входных потоков уже отсортирован (от меньшего к большему).5657#### `heapq.nlargest(n, iterable, key=None)`5859Возвращает список из *n* наибольших элементов из набора данных, заданного *iterable*. Если указан *key*, он задаёт функцию одного аргумента, используемую для извлечения ключа сравнения из каждого элемента итератора: `key=str.lower` Эквивалентно: `sorted(iterable, key=key, reverse=True)[:n]`6061#### `heapq.nsmallest(n, iterable, key=None)`6263Возвращает список из *n* наименьших элементов из набора данных, заданного *iterable*. Если указан *key*, он задаёт функцию одного аргумента, используемую для извлечения ключа сравнения из каждого элемента итератора: `key=str.lower` Эквивалентно: `sorted(iterable, key=key)[:n]`6465Последние две функции работают лучше для небольших значений *n*. Для больших значений эффективнее использовать функцию [`sorted()`](https://python-all.ru/3.3/library/functions.html#sorted). Кроме того, когда `n==1`, эффективнее использовать встроенные функции [`min()`](https://python-all.ru/3.3/library/functions.html#min) и [`max()`](https://python-all.ru/3.3/library/functions.html#max).6667## 8.5.1. Базовые примеры6869Кучную сортировку ([heapsort](https://python-all.ru/3.3/library/heapq.html)) можно реализовать, помещая все значения в кучу, а затем извлекая наименьшие значения одно за другим:7071```python72>>> def heapsort(iterable):73... 'Equivalent to sorted(iterable)'74... h = []75... for value in iterable:76... heappush(h, value)77... return [heappop(h) for i in range(len(h))]78...79>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])80[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]81```8283Элементами кучи могут быть кортежи. Это удобно для присвоения значений сравнения (например, приоритетов задач) вместе с основной отслеживаемой записью:8485```python86>>> h = []87>>> heappush(h, (5, 'write code'))88>>> heappush(h, (7, 'release product'))89>>> heappush(h, (1, 'write spec'))90>>> heappush(h, (3, 'create tests'))91>>> heappop(h)92(1, 'write spec')93```9495## 8.5.2. Примечания по реализации очереди с приоритетом9697[Очередь с приоритетом](https://python-all.ru/3.3/library/heapq.html) – распространённое применение кучи, и она ставит несколько задач при реализации:9899- Устойчивость сортировки: как добиться, чтобы две задачи с одинаковыми приоритетами возвращались в порядке их добавления?100- Сравнение кортежей нарушается для пар (приоритет, задача), если приоритеты равны, а задачи не имеют порядка сравнения по умолчанию.101- Если приоритет задачи изменился, как переместить её на новую позицию в куче?102- Или если ожидающую задачу нужно удалить, как найти её и убрать из очереди?103104Решение первых двух задач – хранить записи в виде списка из трёх элементов: приоритет, счётчик записей и задача. Счётчик записей служит разрешителем равенства, так что две задачи с одинаковым приоритетом возвращаются в порядке их добавления. А поскольку все счётчики записей различны, сравнение кортежей никогда не попытается сравнивать задачи напрямую.105106Остальные трудности связаны с поиском ожидающей задачи и изменением её приоритета или полным удалением. Задачу можно найти с помощью словаря, указывающего на запись в очереди.107108Удаление записи или изменение её приоритета сложнее, так как это нарушит инварианты структуры кучи. Поэтому возможное решение – пометить запись как удалённую и добавить новую запись с изменённым приоритетом:109110```python111pq = [] # список записей, организованных в виде кучи112entry_finder = {} # отображение задач на записи113REMOVED = '<removed-task>' # заполнитель для удалённой задачи114counter = itertools.count() # уникальный счётчик последовательности115116def add_task(task, priority=0):117 'Add a new task or update the priority of an existing task'118 if task in entry_finder:119 remove_task(task)120 count = next(counter)121 entry = [priority, count, task]122 entry_finder[task] = entry123 heappush(pq, entry)124125def remove_task(task):126 'Mark an existing task as REMOVED. Raise KeyError if not found.'127 entry = entry_finder.pop(task)128 entry[-1] = REMOVED129130def pop_task():131 'Remove and return the lowest priority task. Raise KeyError if empty.'132 while pq:133 priority, count, task = heappop(pq)134 if task is not REMOVED:135 del entry_finder[task]136 return task137 raise KeyError('pop from an empty priority queue')138```139140## 8.5.3. Теория141142Кучи – это массивы, для которых `a[k] <= a[2*k+1]` и `a[k] <= a[2*k+2]` для всех *k*, считая элементы с нуля. Для сравнения несуществующие элементы считаются бесконечными. Интересное свойство кучи заключается в том, что `a[0]` всегда является её наименьшим элементом.143144Странный инвариант выше предназначен для эффективного представления турнира в памяти. Числа ниже – это *k*, а не `a[k]`:145146```python147 0148149 1 2150151 3 4 5 6152153 7 8 9 10 11 12 13 1415415515 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30156```157158В дереве выше каждая ячейка *k* находится над `2*k+1` и `2*k+2`. В обычном бинарном турнире, который мы видим в спорте, каждая ячейка является победителем над двумя ячейками, которые она возглавляет, и мы можем проследить победителя вниз по дереву, чтобы увидеть всех его противников. Однако во многих компьютерных приложениях таких турниров нам не нужно отслеживать историю победителя. Чтобы быть более эффективными по памяти, когда победитель продвигается вверх, мы пытаемся заменить его чем-то другим на более низком уровне, и правило становится таким, что ячейка и две ячейки, которые она возглавляет, содержат три разных элемента, но верхняя ячейка «выигрывает» у двух нижних ячеек.159160Если этот инвариант кучи всегда сохраняется, то индекс 0, очевидно, является общим победителем. Самый простой алгоритмический способ удалить его и найти «следующего» победителя – переместить какого-то проигравшего (скажем, ячейку 30 на диаграмме выше) на позицию 0, а затем просеивать этот новый 0 вниз по дереву, обменивая значения, пока инвариант не будет восстановлен. Это, очевидно, логарифмическая зависимость от общего количества элементов в дереве. Перебирая все элементы, получается сортировка O(n log n).161162Приятная особенность такой сортировки: можно эффективно вставлять новые элементы во время её выполнения, при условии, что вставляемые элементы не «лучше» последнего извлечённого нулевого элемента. Это особенно полезно в сценариях моделирования, где дерево содержит все поступающие события, а условие «выигрыша» означает наименьшее запланированное время. Когда событие планирует выполнение других событий, они планируются на будущее, поэтому легко помещаются в кучу. Таким образом, куча – хорошая структура для реализации планировщиков (именно это я использовал в своём MIDI-секвенсоре :-)).163164Различные структуры для реализации планировщиков были тщательно изучены, и кучи для этого хороши: они достаточно быстры, скорость почти постоянна, и наихудший случай мало отличается от среднего. Однако существуют и другие представления, которые в целом более эффективны, хотя наихудшие случаи могут быть ужасными.165166Кучи также очень полезны при большой сортировке на диске. Вероятно, всем известно, что большая сортировка подразумевает создание «прогонов» (предварительно отсортированных последовательностей, размер которых обычно связан с объемом оперативной памяти), за которыми следуют проходы слияния для этих прогонов, причем слияние часто организовано очень умно [\[1\]](https://python-all.ru/3.3/library/heapq.html#id2). Очень важно, чтобы начальная сортировка создавала как можно более длинные прогоны. Турниры – хороший способ для этого. Если, используя всю доступную память для проведения турнира, заменять и просеивать элементы, которые вписываются в текущий прогон, то получаются прогоны, вдвое превышающие размер памяти для случайного ввода, и гораздо лучше для ввода с нечеткой упорядоченностью.167168Более того, если вы выводите нулевой элемент на диск и получаете входное значение, которое не помещается в текущий турнир (потому что оно «выигрывает» у последнего выведенного значения), то оно не может поместиться в кучу, и размер кучи уменьшается. Освободившуюся память можно сразу с умом использовать для постепенного построения второй кучи, которая растёт ровно с той же скоростью, с какой тает первая. Когда первая куча полностью исчезает, вы переключаетесь на вторую и начинаете новую серию. Умно и весьма эффективно!169170Одним словом, кучи – полезные структуры данных, которые стоит знать. Я использую их в нескольких приложениях и считаю, что полезно иметь модуль «heap» под рукой. :-)171172Сноски173174| [\[1\]](https://python-all.ru/3.3/library/heapq.html#id1) | Современные алгоритмы балансировки дисков раздражают больше, чем впечатляют, и это следствие возможностей позиционирования дисков. На устройствах без произвольного доступа, таких как большие ленточные накопители, ситуация была совсем иной, и приходилось проявлять большую изобретательность, чтобы заранее гарантировать, что каждое перемещение ленты будет максимально эффективным (то есть наилучшим образом способствует «продвижению» слияния). Некоторые ленты умели даже читать в обратном направлении, и это использовали, чтобы избежать перемотки. Поверьте, по-настоящему хорошие ленточные сортировки были впечатляющим зрелищем! Во все времена сортировка была Великим Искусством! :-) |175| --- | --- |176