Двоичная куча: как устроена и почему хранится в массиве

Коротко

Куча отвечает на один вопрос — «какой элемент самый маленький?» — и делает это мгновенно. Всё остальное она умеет посредственно, и в этом её смысл.

Свойство кучи

Двоичная куча это полное двоичное дерево с одним правилом:

Значение в каждом узле не больше значений его детей (для min-кучи).

        1
      /   \
     3     5
    / \   /
   4   8 7

Обратите внимание, чего здесь нет: упорядоченности между братьями. Число 3 меньше 5, но это случайность — куча этого не требует. Единственная гарантия — предок не больше потомка. Поэтому минимум всегда в корне, а вот второй по величине элемент может быть где угодно на втором уровне.

Это ключевое отличие от двоичного дерева поиска, которое поддерживает полный порядок и потому дороже в обслуживании.

Дерево, которое живёт в массиве

Самое элегантное в куче — она не хранит ни одного указателя. Дерево полное (заполняется слева направо без дыр), поэтому его можно уложить в массив по уровням.

дерево:        1
             /   \
            3     5
           / \   /
          4   8 7

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

Связи вычисляются арифметикой:

parent(i) = (i - 1) // 2
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2

Проверим: у элемента с индексом 1 (значение 3) дети на позициях 3 и 4 — это 4 и 8. Совпадает с рисунком.

Отсюда два бонуса: экономия памяти (нет указателей) и отличная работа с кешем процессора, потому что элементы лежат подряд.

Две операции, на которых всё держится

Просеивание вверх (при вставке)

Новый элемент кладём в конец массива — это единственное место, где полнота дерева не нарушится. Он может оказаться меньше родителя, тогда меняем их местами и повторяем, пока свойство не восстановится.

вставляем 2 в [1, 3, 5, 4, 8, 7]

[1, 3, 5, 4, 8, 7, 2]   2 попала на индекс 6, родитель — индекс 2 (значение 5)
[1, 3, 2, 4, 8, 7, 5]   2 < 5 → меняем
                        новый родитель — индекс 0 (значение 1)
                        2 > 1 → останавливаемся

Путь от листа до корня — высота дерева, то есть O(log n).

Просеивание вниз (при извлечении)

Минимум лежит в корне, его и отдаём. Но корень нельзя просто удалить — образуется дыра. Вместо этого на его место ставим последний элемент массива, а потом «опускаем» его вниз, меняя с меньшим из детей.

извлекаем минимум из [1, 3, 2, 4, 8, 7, 5]

отдаём 1, на его место ставим 5 (последний):
[5, 3, 2, 4, 8, 7]      дети 5 — это 3 и 2, меньший 2
[2, 3, 5, 4, 8, 7]      меняем, детей у индекса 2 нет — стоп

Тоже O(log n).

Реализация на Python

class MinHeap:
    def __init__(self) -> None:
        self._data: list[int] = []

    def __len__(self) -> int:
        return len(self._data)

    def peek(self) -> int:
        if not self._data:
            raise IndexError('куча пуста')
        return self._data[0]           # минимум всегда в корне, O(1)

    def push(self, value: int) -> None:
        self._data.append(value)
        self._sift_up(len(self._data) - 1)

    def pop(self) -> int:
        if not self._data:
            raise IndexError('куча пуста')

        top = self._data[0]
        last = self._data.pop()

        if self._data:                 # если что-то осталось
            self._data[0] = last
            self._sift_down(0)

        return top

    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self._data[i] >= self._data[parent]:
                break
            self._data[i], self._data[parent] = self._data[parent], self._data[i]
            i = parent

    def _sift_down(self, i: int) -> None:
        n = len(self._data)

        while True:
            smallest = i
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and self._data[child] < self._data[smallest]:
                    smallest = child

            if smallest == i:
                break

            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest


heap = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
    heap.push(x)

print([heap.pop() for _ in range(len(heap))])
# [1, 2, 3, 5, 8, 9]

Построение за O(n), а не O(n log n)

Очевидный способ построить кучу из массива — вставлять элементы по одному: n вставок по O(log n) даёт O(n log n).

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

def heapify(arr: list[int]) -> None:
    n = len(arr)
    # последний родитель — это (n // 2) - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

Кажется, что это тоже O(n log n) — n/2 просеиваний по O(log n). Но оценка грубая: большинство узлов находятся у самого низа дерева, и просеивать их почти некуда.

Точный подсчёт: на уровне h находится n/2^(h+1) узлов, каждый просеивается не больше чем на h шагов. Сумма

Σ h · n / 2^(h+1)  =  n · Σ h / 2^(h+1)  ≤  2n

Ряд сходится, и итог — O(n). Это неочевидный, но важный результат: именно он делает пирамидальную сортировку конкурентоспособной.

heapq: готовая реализация в Python

Писать кучу руками нужно только для понимания. В стандартной библиотеке есть heapq:

import heapq

nums = [5, 3, 8, 1, 9, 2]
heapq.heapify(nums)            # O(n), на месте

heapq.heappush(nums, 0)
print(heapq.heappop(nums))     # 0
print(nums[0])                 # минимум без извлечения

# k наименьших / наибольших
print(heapq.nsmallest(3, [5, 3, 8, 1, 9]))   # [1, 3, 5]
print(heapq.nlargest(3, [5, 3, 8, 1, 9]))    # [9, 8, 5]

Важная особенность: heapq реализует только min-кучу. Для max-кучи есть два приёма:

# 1. хранить со знаком минус
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
largest = -heapq.heappop(max_heap)

# 2. хранить кортежи (приоритет, значение)
tasks = []
heapq.heappush(tasks, (-priority, task))

Где применяется

Приоритетная очередь — прямое назначение. Задачи с наивысшим приоритетом извлекаются первыми.

Алгоритм Дейкстры — на каждом шаге нужна ближайшая непосещённая вершина. Без кучи алгоритм работал бы за O(V²) вместо O(E log V).

Алгоритм Прима для минимального остовного дерева — та же схема.

Пирамидальная сортировка — построить кучу за O(n), потом n раз извлечь минимум.

Top-K элементов — вместо сортировки всего массива за O(n log n) держим кучу размера k и получаем O(n log k).

Планировщики задач и таймеры в операционных системах.

Чего куча не умеет

Найти произвольный элемент. Только линейным перебором за O(n) — порядок между братьями не определён.

Найти второй по величине быстро. Он на втором уровне, но какой именно из двух — неизвестно без сравнения.

Обойти в отсортированном порядке. Нужно извлекать по одному, разрушая кучу.

Если нужны эти операции — берите двоичное дерево поиска или отсортированный массив.

Частые ошибки

Извлечение корня без замены последним элементом. Дерево перестанет быть полным, и арифметика индексов сломается.

pop() из списка до проверки на пустоту. В реализации выше порядок важен: сначала снимаем последний, потом проверяем, осталось ли что-то.

Просеивание вверх при извлечении. Направления путать нельзя: вставка — вверх, извлечение — вниз.

Попытка сделать max-кучу через reverse=True. У heapq такого параметра нет, нужен трюк со знаком.

Что запомнить

• Куча — полное двоичное дерево, где предок не больше потомков.
• Хранится в массиве без указателей: дети узла i лежат на 2i+1 и 2i+2.
• Вставка и извлечение — O(log n), просмотр минимума — O(1).
• Построение из готового массива стоит O(n), а не O(n log n).
• В Python используйте heapq; для max-кучи храните значения со знаком минус.
• Куча не умеет искать произвольный элемент — это не её задача.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→