Что такое куча (Heap) в Python

В Python куча (heap) — это специальная структура данных, реализованная через модуль heapq, которая представляет собой бинарную минимальную кучу. Это означает, что наименьший элемент всегда находится в корне (индекс 0), что позволяет эффективно извлекать и добавлять элементы за O(log n).

Основные операции:

• heapq.heappush(heap, item) — добавляет элемент в кучу.
• heapq.heappop(heap) — извлекает и возвращает наименьший элемент.
• heapq.heapify(list) — преобразует список в кучу за O(n).

Пример:

import heapq

data = [5, 3, 8, 1, 2]
heapq.heapify(data)  # Преобразуем в кучу: [1, 2, 8, 3, 5]

heapq.heappush(data, 0)  # Добавляем 0: [0, 2, 1, 3, 5, 8]
print(heapq.heappop(data))  # Извлекаем 0, куча: [1, 2, 8, 3, 5]