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=' ')

Документация. Примеры

[python-standart-library]

>>> На главную