Source: Heapq - двоичная куча

← Rendered

markdown source:

---
description: heapq в стандартной библиотеке python
tags: python-standart-library python
title: Heapq - двоичная куча
---
В стандартной библиотеке python реализован вариант двоичной кучи, при котором гарантируется, что значение в любом родительском узле древовидной структуры кучи не больше, чем значение в любом из его дочерних, так называемая min-heapq.

Контейнер позволяет производить эффективные операции над упорядоченным содержимым на месте, при условии что куча упорядочена корректно.

Для создания кучи доступно два метода: `heappush()` и `heapify()`. Первый позволяет добавлять элементы в кучу поэлементно с сохранением порядка сортировки в куче. Когда последовательность уже в памяти, более эффективным является второй метод.

Метод `heappop()` извлекает и удаляет из кучи наименьший элемент. `heapreplace()` удаляет и заменяет элемент на новый на месте.

`nlargest()` и `nsmalest()` позволяет получить n наибольших и наименьших элементов. Это эффектино только для относительно небольших n.

`heappushpop()` комбинированный метод - сначала добавляем элемент, затем удаляем и возвращаем наименьший

Метод `merge()` позволяет эффективно смержить несколько отсортированных последовательностей в одну отсортированную последовательность. Пример объединения последовательностей через кучу (расход памяти зависит только от числа последовательностей)

```python
import heapq
import random

data = []
for i in range(4):
    new_data = list(random.sample(range(1, 101), 5))
    new_data.sort()
    data.append(new_data)

for i, d in enumerate(data):
    print('{}: {}'.format(i, d))

print('\nMerged:')
for i in heapq.merge(*data):
    print(i, end=' ')
```

[Документация](https://docs.python.org/3/library/heapq.html?highlight=heapq#module-heapq). [Примеры](https://docs.python.org/3/library/heapq.html?highlight=heapq#basic-examples)

[[python-standart-library]]


[python-standart-library]: ../lists/python-standart-library "Стандартная библиотека python и полезные ресурсы"