Главное преимущество heap: array без указателей

Heap — это бинарное дерево, но хранится в обычном массиве. Никаких указателей left/right. Никаких узлов, размещённых случайно в heap’е процесса. Только массив value’ов.

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

соответствующее дерево:

         2 (idx 0)
        / \
       5   3      (idx 1, 2)
      / \  /
     8  6 4       (idx 3, 4, 5)
     /
    9             (idx 6 — продолжение последнего уровня)

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

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

Зная индекс узла в массиве, вычисляем индексы parent, left и right детей:

def parent(i):
    return (i - 1) // 2

def left_child(i):
    return 2 * i + 1

def right_child(i):
    return 2 * i + 2

Эти формулы работают для любого индекса в массиве. Только корень (i=0) не имеет parent (формула дала бы -0, нужно отдельно проверять).

Доказательство, почему именно эти формулы — через индукцию по уровням:

• Уровень 0: индексы 0..0, 1 узел.
• Уровень 1: индексы 1..2, 2 узла.
• Уровень 2: индексы 3..6, 4 узла.
• Уровень k: индексы 2^k - 1 .. 2^(k+1) - 2, 2^k узлов.

Дети узла i ∈ уровень k лежат на уровне k+1, в позициях, которые легко вычислить через арифметику геометрической прогрессии. Результат — простые формулы 2i+1 и 2i+2.

Доступ к узлу — sequential

Главное практическое преимущество array layout — cache locality:

сравнение:

linked tree:
   адрес узла A:   0x7f8a3000
   адрес node.left: 0x7f8a4500   <- случайно где-то в heap'е процесса
   адрес node.right: 0x7f8a1800   <- ещё дальше
   каждый переход — потенциальный cache miss

array layout:
   адрес node[5]: arr_start + 5*8 = arr_start + 40
   адрес node[6]: arr_start + 6*8 = arr_start + 48  <- соседний байт!
   доступ к соседнему индексу — это L1 cache hit, ~1ns

Sift up/down (см. следующий урок) делает 1-log(n) переходов по массиву с регулярным паттерном. CPU prefetcher предсказывает эти переходы и заранее тащит данные в L1/L2 кеш. Это даёт огромное практическое ускорение.

Эксперимент: heap vs linked tree

Сравним скорость heappush для array-based heapq и условного linked tree:

import heapq
import time

class LinkedNode:
    __slots__ = ('value', 'left', 'right')
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

# Простой linked min-heap (упрощённая имплементация)
class LinkedHeap:
    def __init__(self):
        self.root = None
        self.size = 0
        self.last = None
    
    # упрощённый push (без правильного complete-инварианта)
    # просто для демонстрации стоимости alloc'ов
    def push(self, value):
        new_node = LinkedNode(value)
        if self.root is None:
            self.root = new_node
        else:
            # упрощённо: вставка в конец
            self._insert(self.root, new_node)
        self.size += 1
    
    def _insert(self, root, node):
        # BFS до первого free слота — это упрощение
        from collections import deque
        q = deque([root])
        while q:
            cur = q.popleft()
            if cur.left is None:
                cur.left = node
                return
            if cur.right is None:
                cur.right = node
                return
            q.append(cur.left)
            q.append(cur.right)

# array-based
n = 100_000
h = []
start = time.perf_counter()
for i in range(n):
    heapq.heappush(h, i)
t_heapq = time.perf_counter() - start

print(f"heapq (array): {t_heapq*1000:.0f} ms")
# ~30 ms

# linked: на 100K elements это уже больно
n_small = 5_000
lh = LinkedHeap()
start = time.perf_counter()
for i in range(n_small):
    lh.push(i)
t_linked = time.perf_counter() - start

print(f"linked tree (just allocs + BFS): {t_linked*1000:.0f} ms for {n_small}")
# ~500-1000 ms — катастрофически медленнее

Разница на одинаковых данных: heapq на 100K элементах ~30ms, linked tree на 5K элементах ~500ms. В 30x больше работы на 1/20 данных — это и есть цена потери cache locality + alloc’ов.

Память: array vs linked

Память тоже отличается в разы:

heap из 1M int'ов:

array-based (Python list of ints):
- list overhead: ~56 байт
- каждый int в Python: ~28 байт, но CPython caches small ints
- для 1M unique ints: ~28 MB
- если int'ы маленькие (<256), почти бесплатно — shared singleton'ы

linked tree:
- 1M узлов
- каждый узел: ~56 байт (header) + value + 2 указателя = ~88 байт
- итого: ~88 MB

Array экономит ~3× на памяти. Плюс не фрагментирует heap процесса — все ячейки массива лежат подряд, а не разбросаны.

Когда array layout не работает

Array layout идеален для complete binary trees, где нет «дырок». Если в дереве могут быть пустые позиции, массив будет содержать None’ы — трата памяти.

Для skewed дерева (вырожденного, как linked list) array layout катастрофичен: на N узлов потребуется массив размера 2^N - 1 (пустые позиции для гипотетических соседей).

К счастью, heap всегда complete — это его инвариант. Поэтому array layout — оптимальный выбор именно для heap.

Сегментные деревья тоже используют array layout: они «полные» по построению, и для интервальных queries это самая эффективная структура.

BST обычно не complete (зависит от вставок), поэтому хранится linked. Исключения — сбалансированные деревья поверх массива, но это редкость.

Размер heap: dynamic array

Python list умеет автоматически расти при достижении capacity (см. модуль 5). Heap наследует это: heappush в полный heap триггерит resize массива. Стоимость amortized O(1) per push.

Если вы знаете заранее, сколько элементов будет в heap’е, можно заранее аллоцировать массив:

# не оптимизированно — Python list растёт автоматически
h = []
for i in range(1_000_000):
    heapq.heappush(h, i)

# pre-allocated
h = [0] * 1_000_000   # пустой массив нужного размера
# но в heap'е нет direct API для pre-size; обычно используют heapify

Лучший трюк — построить heap сразу из существующего массива через heapify:

data = list(range(1_000_000, 0, -1))   # обратный порядок
heapq.heapify(data)                     # сделать heap'ом за O(n)
# теперь data — валидная min-heap

heapify работает за O(n), а не O(n log n) — это удивительный факт, который разберём в уроке 04.

Heap в HashMap’ах через handle

В сложных алгоритмах (Dijkstra с decrease-key) нужно обновлять приоритет элемента в heap’е. Чистый heap не поддерживает «найти элемент» за O(log n) — нужно знать его индекс.

Решение — handle-based heap: хранится дополнительный dict {element -> index_in_heap}, обновляемый при каждом sift up/down. Это даёт обновление приоритета за O(log n).

class IndexedHeap:
    def __init__(self):
        self.heap = []                    # массив (priority, item)
        self.index = {}                   # item -> index в массиве

    def push(self, priority, item):
        self.heap.append((priority, item))
        self.index[item] = len(self.heap) - 1
        self._sift_up(len(self.heap) - 1)

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        self.index[self.heap[i][1]] = i
        self.index[self.heap[j][1]] = j
    
    # _sift_up и остальное аналогично базовому heap'у, но с update индексов

Это не входит в стандартный heapq, нужно писать свой или брать стороннюю либу. Но идея простая: array layout + дополнительный hash для поиска индекса.

Применение: heapq.merge для k-way merge

Python heapq.merge использует heap для слияния нескольких отсортированных итераторов в один отсортированный поток:

import heapq

streams = [
    [1, 5, 9, 13],
    [2, 6, 10, 14],
    [3, 7, 11, 15],
    [4, 8, 12, 16],
]

merged = list(heapq.merge(*streams))
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Внутри: heap из K «текущих голов» потоков. На каждый шаг extract-min (минимум из голов), advance тот поток, у которого извлекли. Сложность O(N log K), память O(K). Это основа external sort: сортировка файла, не помещающегося в RAM.

Попробуй сам

import heapq

# 1. Реализуйте формулы навигации
def parent(i): return (i - 1) // 2
def left(i): return 2 * i + 1
def right(i): return 2 * i + 2

# проверьте на конкретном heap'е
h = [1, 3, 5, 7, 9, 11, 13]   # валидный min-heap
print(f"size: {len(h)}")
for i in range(len(h)):
    p = parent(i) if i > 0 else None
    l = left(i) if left(i) < len(h) else None
    r = right(i) if right(i) < len(h) else None
    p_val = h[p] if p is not None else 'N/A'
    l_val = h[l] if l is not None else 'N/A'
    r_val = h[r] if r is not None else 'N/A'
    print(f"i={i} val={h[i]}: parent={p_val}, left={l_val}, right={r_val}")

# 2. Проверка heap-инварианта вручную
def is_min_heap(arr):
    for i in range(len(arr)):
        l = 2 * i + 1
        r = 2 * i + 2
        if l < len(arr) and arr[i] > arr[l]:
            return False
        if r < len(arr) and arr[i] > arr[r]:
            return False
    return True

print(is_min_heap([1, 3, 5, 7, 9]))    # True
print(is_min_heap([5, 1, 3, 7, 9]))    # False — 5 > 1

# 3. Heapify из произвольного массива
import random
data = list(range(100))
random.shuffle(data)
print(f"Before: {data[:10]}")
heapq.heapify(data)
print(f"After:  {data[:10]}")
print(f"Is valid heap: {is_min_heap(data)}")

# 4. K-way merge
streams = [sorted(random.sample(range(100), 10)) for _ in range(4)]
print(f"4 sorted streams, each 10 elements")
merged = list(heapq.merge(*streams))
print(f"Merged: {len(merged)} total elements")
print(f"Is sorted: {merged == sorted(merged)}")

# 5. Сравнение памяти array vs linked
import sys

# array heap
arr_heap = list(range(1000))
print(f"\nArray heap (1K ints): {sys.getsizeof(arr_heap)} bytes")
# linked tree: 1000 nodes, каждый ~56 байт
print(f"Linked equivalent: ~{1000 * 56} bytes (estimated)")

В следующем уроке разберём операции push/pop в деталях: что такое sift up и sift down, почему они работают за O(log n), и как именно поддерживают heap-инвариант.