Что такое Heap

Heap (куча) — это специализированная структура данных, представляющая собой почти полное бинарное дерево, удовлетворяющее свойству кучи: для min-heap каждый родительский узел меньше или равен своим потомкам, для max-heap — наоборот.

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

• heapify — преобразование списка в кучу за O(n)
• heappush — добавление элемента за O(log n)
• heappop — извлечение корня (min/max) за O(log n)

Пример с heapq (min-heap в Python):

import heapq

nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)  # [1, 1, 4, 3, 5]
heapq.heappush(nums, 2)  # [1, 1, 2, 3, 5, 4]
print(heapq.heappop(nums))  # 1

Используется в алгоритмах (например, Dijkstra), сортировке (Heapsort) и приоритетных очередях. В Python heapq реализует min-heap, для max-heap элементы инвертируются.