Куча (heap)

Куча — это полное двоичное дерево, в котором каждый родитель не больше (min-heap) или не меньше (max-heap) своих детей. Хранится в массиве; корень — минимальный или максимальный элемент. Основа приоритетной очереди.

Сложность: вставка и извлечение корня — O(log n); просмотр корня — O(1); построение из массива — O(n). Память: O(n).

import heapq
h = [5, 1, 8, 3]
heapq.heapify(h)        # O(n) -> min-heap
heapq.heappush(h, 2)    # O(log n)
print(heapq.heappop(h)) # O(log n) -> 1 (минимум)