Хранение дерева в массиве на практике: реализация кучи, сегментного дерева и статического BST

Дерево укладывается в обычный массив без единого указателя, когда оно полное или почти полное. Связи между узлами считаются арифметикой: потомки узла с индексом i лежат на позициях 2i+1 и 2i+2 при нумерации с нуля, родитель - на позиции (i-1)/2. На этом представлении построены бинарная куча, сегментное дерево и статический бинарный поиск, собранный из отсортированного набора.

В статье четыре рабочих блока кода: класс кучи, который переключается между min-heap и max-heap одним флагом, сегментное дерево с суммой на отрезке и обновлением точки, статический BST из отсортированного массива. Для каждого - команда запуска и ожидаемый вывод. Отдельно разбираем ошибки, которые дают тихий неверный результат вместо исключения, и чек-лист из 10 пунктов перед выкатом.

Зачем хранить дерево в массиве и как это работает

Массив и дерево связывает одна идея: если дерево заполняет уровни слева направо без пропусков, позиция узла однозначно задаёт его место в иерархии. Переход к потомку превращается в умножение и сложение, переход к родителю - в целочисленное деление. Ссылки не нужны вообще.

Выигрыш не только в арифметике. Все узлы лежат в одном непрерывном блоке памяти, поэтому процессор подтягивает их линиями кэша и не тратит такты на переходы по случайным адресам. Для 10^6 узлов типа int64 массив занимает 8 МБ. Узлы со ссылками на потомков в том же количестве потребуют минимум 24 байта на элемент (два указателя по 8 байт, значение и выравнивание), то есть около 24 МБ, плюс работа сборщика мусора при каждом обновлении структуры.

Формулы индексации: 0-based против 1-based

Две системы нумерации отличаются сдвигом корня. Формулы нельзя смешивать в одном коде.

Пример на массиве из 7 элементов [4, 2, 6, 1, 3, 5, 7]. Узел с индексом 0 в системе с нуля содержит значение 4 и имеет потомков 1 и 2 со значениями 2 и 6. Узел с индексом 1 в системе с единицы содержит то же значение 4 и имеет потомков 2 и 3, то есть снова 2 и 6. Результат одинаковый, отличаются только числа.

Подъём и спуск обязаны использовать формулы одной системы. Проверка согласованности занимает пару строк и ловит смешение сразу:

for i in range(n):
    children = (2 * i + 1, 2 * i + 2) if zero_based else (2 * i, 2 * i + 1)
    for c in children:
        if c < n:
            assert parent(c) == i

Классическая ошибка: потомки взяты из системы с нуля, а родитель - из системы с единицы, то есть i/2. Лист с индексом 2 имеет фактического родителя (2-1)/2 = 0, а формула i/2 выдаёт 1. Подъём после sift-up уходит в чужую ветку, куча перестаёт быть кучей, и никакое исключение не срабатывает.

Разбор формул, условий применимости и критериев выбора между массивом и связным представлением собран в отдельном материале: хранение дерева в массиве: формулы и условия применимости.

Когда массив проигрывает указателям

Массив хранит дерево дёшево, пока узлы заполняют уровни подряд. Предпосылку ломают два случая.

• Разреженное дерево. Пропуски приходится забивать заполнителями, и доля полезных слотов падает. Порог, после которого выгоднее словарь, зависит от заполнения.
• Перекос. BST из 1000 ключей, отсортированных по возрастанию, вырождается в цепочку высотой 999. Максимальный индекс в массивной раскладке растёт как 2^h, и уже при h = 60 это примерно 1.15 * 10^18. Такой массив не поместится ни в память, ни в int64.

Критерий выбора простой. Если число узлов близко к 2^h - 1 и уровни заполнены подряд, берите массив. Если форма произвольная, узлы вставляются и удаляются в случайных местах или дерево заметно разрежено, берите указатели, B-дерево или хеш-таблицу. Три рабочих способа хранить неполное дерево в массиве, включая индексы-заполнители, словарь и динамическое расширение, разобраны в статье разреженное дерево в массиве.

Реализация кучи на массиве: код и проверка

Куча по определению полное бинарное дерево, поэтому массив не тратит ни одного лишнего слота. Класс ниже поддерживает оба режима одной парой операций sift-up и sift-down.

class Heap:
    def __init__(self, data=(), is_max=False):
        self.a = list(data)
        self.is_max = is_max
        for i in range(len(self.a) // 2 - 1, -1, -1):
            self.sift_down(i)

    def _higher(self, i, j):
        # True, если элемент i должен стоять выше элемента j
        return self.a[i] > self.a[j] if self.is_max else self.a[i] < self.a[j]

    def peek(self):
        if not self.a:
            raise IndexError("empty heap")
        return self.a[0]

    def push(self, x):
        self.a.append(x)
        i = len(self.a) - 1
        while i > 0:
            p = (i - 1) // 2
            if not self._higher(i, p):
                break
            self.a[i], self.a[p] = self.a[p], self.a[i]
            i = p

    def pop(self):
        if not self.a:
            raise IndexError("empty heap")
        top = self.a[0]
        last = self.a.pop()
        if self.a:
            self.a[0] = last
            self.sift_down(0)
        return top

    def sift_down(self, i):
        n = len(self.a)
        while True:
            l, r = 2 * i + 1, 2 * i + 2
            best = i
            if l < n and self._higher(l, best):
                best = l
            if r < n and self._higher(r, best):
                best = r
            if best == i:
                return
            self.a[i], self.a[best] = self.a[best], self.a[i]
            i = best

Сборка кучи из готового массива - это heapify за O(n), а не n вызовов push за O(n log n). Цикл идёт от последнего внутреннего узла n/2 - 1 к корню: каждый узел спускается вниз уже по готовым поддеревьям.

Min-heap и max-heap: в чём разница на уровне массива

Различие только в компараторе. В min-heap родитель не больше потомков, в max-heap не меньше. Индексация 2i+1 и 2i+2 остаётся той же, поэтому переключение режима - это флаг, а не второй класс с копией кода.

src = [3, 1, 4, 1, 5, 9, 2, 6]
print(Heap(src).a)                # [1, 1, 2, 3, 5, 9, 4, 6]
print(Heap(src, is_max=True).a)   # [9, 6, 4, 1, 5, 3, 2, 1]

Оба массива корректны для своих режимов. В min-heap проверьте свойство вручную: a[1] = 1 не больше a[3] = 3 и a[4] = 5, a[2] = 2 не больше a[5] = 9 и a[6] = 4. Для max-heap в Python часто берут heapq с инвертированным знаком: push(-x) и возврат -pop(). Приём короче, но требует аккуратности с произвольными объектами и с границей диапазона целых чисел, где смена знака даёт переполнение.

Команды проверки кучи после сборки

Сложности операций: peek за O(1), push и pop за O(log n), heapify за O(n). Свойство кучи проверяется обходом всех внутренних узлов, и эту проверку стоит вынести в unit-тест.

def is_min_heap(a):
    n = len(a)
    for i in range(n // 2):
        l, r = 2 * i + 1, 2 * i + 2
        if l < n and a[i] > a[l]:
            return False
        if r < n and a[i] > a[r]:
            return False
    return True

print("min-heap:", Heap(src).a, "ok" if is_min_heap(Heap(src).a) else "broken")
print("max-heap:", Heap(src, is_max=True).a)

h = Heap(src)
print("pop x3:", [h.pop() for _ in range(3)])

Запуск и ожидаемый вывод:

$ python3 heap.py
min-heap: [1, 1, 2, 3, 5, 9, 4, 6] ok
max-heap: [9, 6, 4, 1, 5, 3, 2, 1]
pop x3: [1, 1, 2]

Для приоритетной очереди храните пары (priority, item) и добавляйте монотонный счётчик вставок в качестве второго ключа: при равных приоритетах сравнение дойдёт до числа и не упрётся в несравнимые объекты.

Сегментное дерево на массиве: диапазонные запросы без указателей

Сегментное дерево живёт в массиве размера 4n, где n - длина исходных данных. Узлы нумеруются с единицы: корень в t[1], потомки узла v - это 2v и 2v+1, каждый узел хранит агрегат своего отрезка.

class SegTree:
    def __init__(self, data):
        self.n = len(data)
        self.t = [0] * (4 * self.n) if self.n else []
        if self.n:
            self._build(1, 0, self.n - 1, data)

    def _build(self, v, l, r, data):
        if l == r:
            self.t[v] = data[l]
            return
        m = (l + r) // 2
        self._build(2 * v, l, m, data)
        self._build(2 * v + 1, m + 1, r, data)
        self.t[v] = self.t[2 * v] + self.t[2 * v + 1]

    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)

    def _query(self, v, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.t[v]
        m = (l + r) // 2
        res = 0
        if ql <= m:
            res += self._query(2 * v, l, m, ql, qr)
        if qr > m:
            res += self._query(2 * v + 1, m + 1, r, ql, qr)
        return res

    def update(self, pos, value):
        self._update(1, 0, self.n - 1, pos, value)

    def _update(self, v, l, r, pos, value):
        if l == r:
            self.t[v] = value
            return
        m = (l + r) // 2
        if pos <= m:
            self._update(2 * v, l, m, pos, value)
        else:
            self._update(2 * v + 1, m + 1, r, pos, value)
        self.t[v] = self.t[2 * v] + self.t[2 * v + 1]

Пример: данные [1, 3, 5, 7, 9, 11]. Запрос суммы на отрезке [1, 4] даёт 3 + 5 + 7 + 9 = 24. После update(2, 10) тот же запрос возвращает 3 + 10 + 7 + 9 = 29. Сложности: build за O(n), query и update за O(log n). Наивный перебор на каждом запросе - O(n), и на потоке событий это первое место, которое упирается в процессор.

Почему размер массива 4n, а не 2n

При разбиении отрезка серединой листья попадают на разную глубину, поэтому максимальный индекс узла превышает 2n. Скрипт ниже печатает точный максимум для разных n.

def max_index(n):
    best, stack = 0, [(1, 0, n - 1)]
    while stack:
        v, l, r = stack.pop()
        best = max(best, v)
        if l == r:
            continue
        m = (l + r) // 2
        stack.append((2 * v, l, m))
        stack.append((2 * v + 1, m + 1, r))
    return best

print("n  max   2n   4n  хватает 2n")
for n in (1, 2, 3, 5, 6, 8, 9, 10, 16):
    mx = max_index(n)
    print(n, mx, 2 * n, 4 * n, "да" if mx < 2 * n else "нет")

$ python3 max_index.py
n  max   2n   4n  хватает 2n
1  1     2     4  да
2  3     4     8  да
3  5     6    12  да
5  9    10    20  да
6  13   12    24  нет
8  15   16    32  да
9  17   18    36  да
10 25   20    40  нет
16 31   32    64  да

Вывод из таблицы: 2n хватает, когда n - степень двойки, и в части соседних случаев. Для n = 6 нужно минимум 14 слотов при 2n = 12, для n = 10 - минимум 26 при 2n = 20. Массив 4n снимает вопрос без анализа формы разбиения. Если память критична, посчитайте max_index для своего n и возьмите максимум из 2n и найденного значения плюс один.

Отличия рекурсивной и итеративной индексации и связь с ленивым проталкиванием разобраны в статье сегментное дерево в массиве: размер 4n и ленивое проталкивание.

Range update и lazy propagation: когда усложнять

Без отложенных операций обновление одного элемента стоит O(log n), а прибавление константы на отрезке - O(n log n), потому что меняются все листья диапазона. Ленивое проталкивание сохраняет прибавку в узле и переносит её к детям только при спуске, за счёт чего диапазонный update становится O(log n).

# t[v] - сумма на отрезке узла v, lazy[v] - отложенная прибавка к отрезку

def apply(self, v, length, delta):
    self.t[v] += delta * length
    self.lazy[v] += delta

def push(self, v, left_len, right_len):
    if self.lazy[v] != 0:
        self.apply(2 * v, left_len, self.lazy[v])
        self.apply(2 * v + 1, right_len, self.lazy[v])
        self.lazy[v] = 0

Цена решения: второй массив, обязательный push в query и update, больше мест для ошибок при спуске. Добавляйте ленивое проталкивание, когда замеры показывают, что диапазонные обновления стали узким местом. Для разовых запросов по статичному массиву достаточно префиксных сумм.

Статический BST на массиве: когда указатели не нужны

Произвольный BST в массив эффективно не укладывается: форма зависит от порядка вставки, а пропуски съедают память. Другой случай - набор ключей известен заранее и отсортирован. Тогда сбалансированное дерево строится за один проход, а поиск идёт по индексам без разыменований.

Построение сбалансированного BST из отсортированного массива

Алгоритм: середина отрезка становится корнем поддерева, левая половина уходит в левое поддерево, правая - в правое. Нумерация с нуля: левый потомок узла i - это 2i+1, правый - 2i+2.

def build_bst(sorted_arr):
    n = len(sorted_arr)
    if n == 0:
        return []
    tree = [None] * (4 * n)

    def build(v, l, r):
        if l > r:
            return
        m = (l + r) // 2
        tree[v] = sorted_arr[m]
        build(2 * v + 1, l, m - 1)
        build(2 * v + 2, m + 1, r)

    build(0, 0, n - 1)
    return tree

print(build_bst([1, 2, 3, 4, 5, 6, 7])[:7])

Вывод: [4, 2, 6, 1, 3, 5, 7]. Корень 4 стоит в позиции 0, его потомки 2 и 6 - в позициях 1 и 2, листья 1, 3, 5, 7 - в позициях с третьей по шестую. Условие поиска выполняется автоматически: для любого узла все ключи левого поддерева меньше, правого - больше.

Ограничение: раскладка без пропусков получается, когда длина набора равна 2^k - 1, то есть 1, 3, 7, 15 и далее. При другой длине часть слотов останется со значением None, и обход обязан их проверять. Когда ключи известны заранее, но их число произвольно, посмотрите способы хранить неполное дерево в массиве: заполнители, словарь или динамическое расширение.

Поиск и обход в статическом BST

def search(tree, value):
    i, steps = 0, 0
    while i < len(tree) and tree[i] is not None:
        steps += 1
        if tree[i] == value:
            return i, steps
        i = 2 * i + 1 if value < tree[i] else 2 * i + 2
    return -1, steps

def inorder(tree, i=0, out=None):
    if out is None:
        out = []
    if i >= len(tree) or tree[i] is None:
        return out
    inorder(tree, 2 * i + 1, out)
    out.append(tree[i])
    inorder(tree, 2 * i + 2, out)
    return out

tree = build_bst([1, 2, 3, 4, 5, 6, 7])
print("search 6:", search(tree, 6))
print("inorder:", inorder(tree))

$ python3 bst_array.py
search 6: (2, 2)
inorder: [1, 2, 3, 4, 5, 6, 7]

Поиск значения 6 занимает две итерации: первый шаг сравнивает с 4 и уходит в правого потомка, второй находит ключ в позиции 2. Высота сбалансированного дерева из n узлов близка к log2(n+1), поэтому поиск работает за O(log n), а in-order обход возвращает исходный отсортированный массив.

Статичность здесь ключевое слово. Вставка ключа сдвигает середины всех отрезков и ломает раскладку. Для меняющегося набора берите указатели, B-дерево или красно-чёрное дерево. Массивный BST оправдан для справочников, которые читаются часто и меняются раз в релиз: таблицы маршрутов, списки кодов ошибок, словари конфигураций.

Типичные ошибки при хранении дерева в массиве и как их отлаживать

Восемь ошибок закрывают почти все инциденты с этой группой структур.

Отладка через assert и unit-тесты

Стресс-тест против наивной реализации ловит большинство ошибок индексации за секунды. Ниже pytest-тест для сегментного дерева: случайные запросы и обновления сверяются с подсчётом суммы по срезу.

import random
from segtree import SegTree

def brute(a, l, r):
    return sum(a[l:r + 1])

def test_segtree_random():
    for _ in range(200):
        n = random.randint(1, 40)
        a = [random.randint(-50, 50) for _ in range(n)]
        st = SegTree(a)
        for _ in range(20):
            l = random.randint(0, n - 1)
            r = random.randint(l, n - 1)
            assert st.query(l, r) == brute(a, l, r), (a, l, r)
            p = random.randint(0, n - 1)
            v = random.randint(-50, 50)
            a[p] = v
            st.update(p, v)

# граничные размеры, на которых чаще всего вылезает off-by-one
for n in (1, 2, 8, 9):
    def test_size(n=n):
        a = [i for i in range(n)]
        st = SegTree(a)
        assert st.query(0, n - 1) == brute(a, 0, n - 1)

Для кучи добавьте отдельный тест на n = 1: после pop куча обязана остаться пустой, а повторный pop - бросить IndexError. Именно этот случай чаще всего роняет сервисы, потому что код пишут под поток задач, а пустая очередь приходит ночью.

Профилирование и бенчмарк на больших данных

Замеряйте на своём железе и своём профиле нагрузки: цифры с чужой машины не переносятся, а соотношение между массивом и указателями зависит от языка, типа данных и шаблона доступа.

python3 -m cProfile -s cumtime heap_bench.py
python3 -m timeit -s "import heapq, random" "a=[random.random() for _ in range(10**6)]; heapq.heapify(a)"

go test -bench=BenchmarkHeap -benchmem ./...

Полезный эксперимент: сравните время heapify и серии query на массиве и на том же дереве, собранном из объектов с указателями. Разница покажет вклад локальности кэша именно на вашем профиле. Результаты сохраните в README сервиса, чтобы следующий инженер не переделывал замер заново.

Где это применяется в продакшене: примеры для DevOps

Ниже типовые задачи, где массивное представление даёт эффект. Внутреннее устройство планировщиков и библиотек меняется от версии к версии, поэтому сверяйте поведение с исходниками того релиза, который у вас в работе.

Куча в планировщиках и rate limiter

• Очереди задач. Планировщики оркестраторов держат набор готовых к запуску задач в очереди с приоритетом, а очередь с приоритетом строится на куче. Если у вас в кластере работает Kubernetes, проверьте очередь планировщика в исходниках своей версии.
• Rate limiter. Когда лимит общий, а клиенты разные, приоритеты запросов удобно держать в куче: на каждом такте берётся самый приоритетный, а лишние возвращаются обратно.
• Мониторинг. Top-K метрик по потоку событий считается min-heap размера K: новый элемент вытесняет вершину, если он больше неё. Память фиксирована, обновление за O(log K).
• Библиотеки. В Python модуль heapq работает напрямую с list, в Go пакет container/heap работает поверх среза и требует от типа методов Len, Less, Swap, Push, Pop. В обоих случаях раскладка 2i+1 и 2i+2 внутри.

Сегментное дерево в аналитике и алертах

Диапазонные запросы по временным рядам: сумма за окно, число событий, максимум latency. При миллионах точек в секунду наивный перебор окна становится узким местом, а дерево отвечает за O(log n).

Оговорка по агрегатам: сегментное дерево корректно работает для операций, которые собираются из частей - сумма, счётчик, минимум, максимум, произведение. Для p95 и других перцентилей оно не подходит напрямую, потому что перцентиль не восстанавливается из перцентилей половин. Там нужны гистограммы или эскизы вроде t-digest. Если делаете алерт на аномалию по скользящему окну, берите агрегат, который складывается.

Статический BST из отсортированного набора закрывает справочные задачи: таблица маршрутов, список кодов ответов, словарь фича-флагов, который читается на каждом запросе и меняется раз в сутки.

Чек-лист перед деплоем кода структур данных

1. Граничные случаи n = 0, n = 1 и n = 2 закрыты тестами и ведут себя предсказуемо.
2. Размер массива достаточен: 4n для сегментного дерева или посчитанный максимум индекса плюс один.
3. Индексация единая: либо с нуля, либо с единицы, смешения нет ни в одной функции.
4. Есть assert на главное свойство структуры: порядок кучи, суммы на отрезках, порядок BST.
5. Есть стресс-тест против наивной реализации на случайных данных.
6. Проверены n, равные степени двойки, и n = степень двойки + 1.
7. Снят замер на реальном объёме: время query, время update, потребление памяти.
8. Заполнители в пропусках заданы явно (None, плюс бесконечность), ноль как маркер не используется.
9. Версии языка и библиотек зафиксированы вместе с тестовым окружением.
10. Есть план отката: флаг функции, канареечный выкат, метрики на latency и долю ошибок.

Граничные случаи, которые ломают прод

Фиксация версий и план отката

Зафиксируйте интерпретатор и зависимости, с которыми прогоняли тесты.

# requirements-dev.txt
pytest==X.Y.Z   # версия из вашего lock-файла

module example/structures

go 1.22

План отката: спрячьте новую структуру за интерфейсом, включите её через флаг функции на канареечной группе узлов, следите за p99 latency и долей ошибок. Возврат к прежней версии должен быть переключением флага, а не деплоем.

Начните с одной задачи: возьмите самый горячий диапазонный запрос в своём сервисе, замените перебор на сегментное дерево из раздела выше, добавьте стресс-тест против наивной суммы и замер до и после. Один такой замер убедительнее любой теории о структурах данных.