Heap — структура с одним минимальным элементом наверху

Heap (куча) — это специализированное бинарное дерево с одним простым правилом — heap property:

Для каждого узла N значение в N ≤ значениям в его детях (min-heap) или ≥ (max-heap).

Эту структуру часто путают с BST (binary search tree). Это разные вещи. Главное различие:

• BST: left < node < right. Это про полный порядок ключей.
• Heap: parent ≤ children (для min-heap). Это про вершину дерева — корень всегда минимум.

В heap левое и правое поддерево не упорядочены между собой. Heap не отвечает на «какой ключ X-й по величине». Он отвечает на «какой минимум» (или максимум).

Что heap делает, и что НЕ делает

Min-heap vs max-heap

Min-heap: корень — минимальный элемент.

        2          <- min элемент наверху
       / \
      5   3
     / \  /
    8  6 4

Max-heap: корень — максимальный.

        8          <- max элемент наверху
       / \
      6   3
     / \  /
    5  2 1

Python heapq реализует только min-heap. Чтобы сделать max-heap, кладите отрицательные значения:

import heapq

# min-heap (default)
mh = []
heapq.heappush(mh, 5)
heapq.heappush(mh, 2)
heapq.heappush(mh, 8)
print(heapq.heappop(mh))   # 2

# max-heap через отрицание
xh = []
heapq.heappush(xh, -5)
heapq.heappush(xh, -2)
heapq.heappush(xh, -8)
print(-heapq.heappop(xh))  # 8

Heap НЕ упорядочен между поддеревьями

Самая частая путаница: новички думают, что в min-heap left subtree < right subtree. Это неверно. Единственный инвариант — parent ≤ child. Между поддеревьями (и в пределах одного уровня) порядок произвольный.

Пример валидной min-heap, где «слева больше, чем справа»:

        2
       / \
      8   3
     / \
    9  10

Это валидно: 2 ≤ 8, 2 ≤ 3, 8 ≤ 9, 8 ≤ 10. Heap property выполнен для каждого узла. Но если бы это был BST, инвариант был бы нарушен — 8 (left subtree) > 3 (right subtree).

Эта «недоупорядоченность» — фича, не баг. Heap проще поддерживать, чем BST: при insert/extract нужно только восстановить локальное parent-child отношение через sift up/down, а не пересортировывать поддеревья.

Зачем нужен heap

Heap — это priority queue (очередь с приоритетом). Главные применения:

1. Top-K: «найди k минимумов/максимумов из стрима». Идеально для real-time analytics.
2. Dijkstra / A*: алгоритмы кратчайшего пути.
3. Task scheduling: «выполнить самую приоритетную задачу» — heap по приоритету.
4. K-way merge: слить N отсортированных потоков в один отсортированный — heap по головам потоков.
5. External sort: для огромных файлов, не помещающихся в RAM.

В DE особенно важно top-K и k-way merge — оба регулярно встречаются.

Структура: complete binary tree

Heap всегда complete binary tree: все уровни кроме последнего заполнены, последний — слева направо без дырок. Это позволяет хранить heap в массиве без указателей:

индекс:  0  1  2  3  4  5  6
массив: [2, 5, 3, 8, 6, 4, 9]

        idx=0 (val=2)
       /             \
    idx=1 (5)     idx=2 (3)
    /     \       /
 idx=3   idx=4  idx=5
 (8)     (6)    (4)

Формулы навигации:

• parent(i) = (i - 1) // 2
• left_child(i) = 2 * i + 1
• right_child(i) = 2 * i + 2

Это и есть array layout для complete binary tree. Деталями займёмся в следующем уроке.

Heap vs BST vs sorted array

Сравним heap с другими структурами для top-K задачи:

Heap выигрывает там, где много insert + extract-min/max и не нужны другие операции. Это и есть priority queue.

BST выигрывает там, где нужны range queries или general search.

Sorted array хорош для read-only или редко меняющихся коллекций.

Применение: top-K из stream

Самый частый DE-кейс. Нужно отслеживать топ-100 событий из потока в миллиард записей. Хранение всех миллиардов в памяти и потом сортировка — не вариант.

Решение через min-heap размера K:

import heapq

def top_k_streaming(stream, k):
    """Возвращает k максимальных элементов потока."""
    heap = []
    for value in stream:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif value > heap[0]:    # больше минимума в heap'е
            heapq.heapreplace(heap, value)
    return sorted(heap, reverse=True)

# на 1M элементах с k=100
import random
stream = [random.random() for _ in range(1_000_000)]
top = top_k_streaming(stream, 100)
print(f"Top-3: {top[:3]}")

Сложность: O(N log K), память O(K). Для N=10^9 и K=100 это ~10^9 * log(100) = ~7*10^9 операций ≈ секунды на M-class CPU. Память — всего 100 элементов вместо миллиарда.

Heap не для поиска

Если нужно «найти, есть ли элемент X в heap’е» — heap плохой выбор. У него нет порядка между поддеревьями, поэтому search — O(n).

import heapq

h = [1, 3, 2, 7, 5, 6, 4]   # это валидный min-heap

# проверка наличия:
print(5 in h)   # работает, но O(n) — линейный обход

Для search используйте set/dict рядом с heap’ом, если нужны обе операции. Это типичный pattern — heap для приоритетов, set для membership.

Эксперимент: heap vs sorted list

import heapq
import time
import bisect

n = 100_000

# 1. heap
h = []
start = time.perf_counter()
for i in range(n):
    heapq.heappush(h, n - i)   # вставляем в reverse порядке
t_heap = time.perf_counter() - start

# 2. sorted list через bisect
lst = []
start = time.perf_counter()
for i in range(n):
    bisect.insort(lst, n - i)
t_list = time.perf_counter() - start

print(f"heap inserts:        {t_heap*1000:.0f} ms")
print(f"sorted list inserts: {t_list*1000:.0f} ms")
print(f"ratio: {t_list/t_heap:.0f}x")

# теперь pop n минимумов
start = time.perf_counter()
while h:
    heapq.heappop(h)
t_heap_pop = time.perf_counter() - start

start = time.perf_counter()
while lst:
    lst.pop(0)   # O(n) — сдвиг
t_list_pop = time.perf_counter() - start

print(f"\nheap pops:           {t_heap_pop*1000:.0f} ms")
print(f"sorted list pop(0):  {t_list_pop*1000:.0f} ms")

Ожидаемые результаты:

• heap insert: ~30 ms
• sorted list insert: ~3000 ms (в 100 раз медленнее из-за O(n) сдвига)
• heap pop: ~50 ms
• sorted list pop(0): ~3000 ms (тоже O(n) сдвиг)

Heap намного быстрее на mutable workload’е. Sorted list хорош только если редко меняется.

Попробуй сам

import heapq

# 1. Создать min-heap из списка и проверить, что root — минимум
data = [5, 3, 8, 1, 9, 2, 7]
heap = data[:]
heapq.heapify(heap)
print(f"after heapify: {heap}")     # [1, 3, 2, 5, 9, 8, 7] или подобное
print(f"min: {heap[0]}")             # 1

# 2. Достать все по порядку — должно получиться отсортированно
result = []
while heap:
    result.append(heapq.heappop(heap))
print(f"sorted by extract: {result}")  # [1, 2, 3, 5, 7, 8, 9]
# это и есть HeapSort

# 3. Top-3 из потока 1M элементов
import random
def top_k(stream, k):
    heap = []
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

stream = [random.randint(1, 10_000_000) for _ in range(1_000_000)]
print(f"Top-3: {top_k(stream, 3)}")

# 4. Max-heap через отрицание
max_heap = []
for x in [3, 7, 1, 8, 5]:
    heapq.heappush(max_heap, -x)
while max_heap:
    print(-heapq.heappop(max_heap), end=' ')   # 8 7 5 3 1
print()

# 5. Heap по составному ключу (priority, item)
tasks = []
heapq.heappush(tasks, (3, "low priority"))
heapq.heappush(tasks, (1, "high priority"))
heapq.heappush(tasks, (2, "medium"))

while tasks:
    p, t = heapq.heappop(tasks)
    print(f"priority {p}: {t}")
# priority 1: high priority
# priority 2: medium
# priority 3: low priority

В следующем уроке разберём, почему heap хранится в массиве — индексные формулы, cache locality, и сравнение с linked tree представлением.