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 элементы инвертируются.