Heapq - двоичная куча
В стандартной библиотеке python реализован вариант двоичной кучи, при котором гарантируется, что значение в любом родительском узле древовидной структуры кучи не больше, чем значение в любом из его дочерних, так называемая min-heapq.
Контейнер позволяет производить эффективные операции над упорядоченным содержимым на месте, при условии что куча упорядочена корректно.
Для создания кучи доступно два метода: heappush() и heapify(). Первый позволяет добавлять элементы в кучу поэлементно с сохранением порядка сортировки в куче. Когда последовательность уже в памяти, более эффективным является второй метод.
Метод heappop() извлекает и удаляет из кучи наименьший элемент. heapreplace() удаляет и заменяет элемент на новый на месте.
nlargest() и nsmalest() позволяет получить n наибольших и наименьших элементов. Это эффектино только для относительно небольших n.
heappushpop() комбинированный метод - сначала добавляем элемент, затем удаляем и возвращаем наименьший
Метод merge() позволяет эффективно смержить несколько отсортированных последовательностей в одну отсортированную последовательность. Пример объединения последовательностей через кучу (расход памяти зависит только от числа последовательностей)
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=' ')