Двоичная куча в массиве: вставка, извлечение минимума и просеивание (sift-up/sift-down)

Что такое двоичная куча и зачем хранить её в массиве

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

Массив [1, 3, 5, 7, 9, 8] - корректная min-heap из шести элементов. Проверяем связки: A[1]=3 не меньше A[0]=1, A[2]=5 не меньше A[0]=1, A[3]=7 не меньше A[1]=3, A[4]=9 не меньше A[1]=3, A[5]=8 не меньше A[2]=5. Порядок элементов частичный: восьмёрка стоит после девятки, и куча от этого не перестаёт быть корректной. Путать кучу с отсортированным массивом не стоит: сортировка даёт полный порядок, куча даёт только гарантию про родителя и его потомков.

Отсутствие ссылок даёт три практических выигрыша. Память: узел хранит только значение, без указателей на родителя и потомков. Скорость: элементы лежат в одном непрерывном блоке, обход уровнями читает соседние адреса и попадает в кэш процессора. Простота: индекс узла одновременно служит его адресом в структуре. Как массив раскладывается в памяти и как работает адресная арифметика, разбираем в статье Массив в оперативной памяти.

Куча лежит в основе приоритетных очередей и кучной сортировки. Минимум доступен за O(1), вставка и извлечение корня занимают O(log n).

Свойство кучи: что именно проверяем

Инвариант min-heap записывается одной строкой: для любого i > 0 выполняется A[parent(i)] <= A[i]. Корень в проверке не участвует: у него нет родителя, и он равен минимуму всего набора.

Возьмём массив [1, 3, 5, 7, 9, 8, 2]. Для i = 6 родитель имеет индекс (6 - 1) / 2 = 2, A[2] = 5, и условие 5 <= 2 нарушено. Остальные пары в порядке. Нарушение появилось ровно в одном месте, в конце массива, потому что связи между уже существовавшими узлами не менялись.

Просеивание и есть локальный ремонт: элемент меняется местами с родителем и поднимается выше, пока условие не выполнится или пока он не окажется в корне.

Формулы переходов к родителю и потомкам

При индексации с нуля: parent(i) = (i - 1) / 2, left(i) = 2 * i + 1, right(i) = 2 * i + 2. При индексации с единицы: parent(i) = i / 2, left(i) = 2 * i, right(i) = 2 * i + 1. Деление целочисленное, остаток отбрасывается.

Смешивание схем - главный источник ошибок off-by-one. Выберите одну нумерацию, зафиксируйте её в комментарии к модулю и напишите тесты на маленьком массиве. Отдельно проверьте поведение на корне. Обращаться к parent(0) не нужно, а если код всё же это делает, результат зависит от языка. В Python оператор // выполняет деление с округлением вниз: он возвращает наибольшее целое, меньшее или равное результату деления, то есть округляет до ближайшего меньшего числа, а не до ближайшего меньшего по абсолютной величине. Поэтому -1 // 2 даёт -1, и такой индекс молча уедет в конец массива или вызовет исключение. Поведение целочисленного деления отрицательных чисел в C, Java и Go в проверенных источниках не подтверждено, поэтому не полагайтесь на него: ставьте проверку i > 0 перед подъёмом.

Вставка элемента в кучу через sift-up

Вставка состоит из двух фаз. Сначала новый элемент дописывается в конец массива, где заведомо есть свободная позиция. Затем включается sift-up: элемент сравнивается с родителем и поднимается, пока свойство кучи не восстановится.

1. Добавьте элемент в конец массива: A[size] = value, после чего увеличьте size на 1.
2. Запомните индекс i добавленного элемента.
3. Пока i > 0 и A[parent(i)] > A[i], меняйте A[i] и A[parent(i)] местами и присваивайте i = parent(i).
4. Остановитесь, когда условие перестало выполняться или i стало равно 0.

Пошаговый пример вставки с индексами

Берём кучу [1, 3, 5, 7, 9, 8], размер 6. Вставляем значение 2.

1. Дописываем в конец: [1, 3, 5, 7, 9, 8, 2], индекс нового элемента 6, размер 7.
2. parent(6) = (6 - 1) / 2 = 2, A[2] = 5. Условие 5 > 2 выполняется, меняем местами элементы с индексами 6 и 2: [1, 3, 2, 7, 9, 8, 5].
3. Теперь значение стоит на индексе 2. parent(2) = 0, A[0] = 1. Условие 1 > 2 ложно, останавливаемся.
4. Итог: [1, 3, 2, 7, 9, 8, 5]. Свойство кучи восстановлено, минимум по-прежнему в корне.

Почему sift-up не может пропустить нарушение

До вставки свойство выполнялось для всех пар родитель-потомок. Новый элемент занял позицию в конце массива, поэтому конфликтовать он может только со своим родителем: связи остальных узлов не изменились, а своих потомков у нового листа нет.

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

Высота кучи определяется как высота двоичного дерева, то есть как количество рёбер в самом длинном простом пути от корня до листа. Поскольку куча - полное двоичное дерево, её высота задаётся формулой floor(log2 n), а для кучи из n элементов высота составляет Θ(log n): слои заполнены полностью, кроме одного частично, и каждый следующий слой содержит вдвое больше вершин. Поэтому sift-up делает не больше log2 n обменов, то есть работает за O(log n). Само добавление в конец динамического массива амортизированно стоит O(1): детали про реаллокацию и коэффициент роста собраны в статье Динамические массивы: рост, реаллокация и цена копирования.

Извлечение минимума через sift-down

Минимум всегда лежит в корне, поэтому достать его просто, а вот восстановить структуру после удаления корня сложнее. На освободившееся место переносят последний элемент массива: так дерево остаётся полным. Затем включается sift-down, который опускает этот элемент до подходящего уровня.

1. Сохраните A[0] в переменную result.
2. Перенесите последний элемент в корень: A[0] = A[size - 1].
3. Уменьшите size на 1.
4. Просеивайте корень вниз: сравнивайте его с меньшим из существующих потомков и обменивайтесь, пока свойство не восстановится или элемент не станет листом.
5. Верните result.

Пошаговый пример извлечения минимума

Куча [1, 3, 2, 7, 9, 8, 5], размер 7. Извлекаем минимум 1.

1. Запоминаем result = 1.
2. Последний элемент 5 переносим в корень: [5, 3, 2, 7, 9, 8], размер 6.
3. Индекс 0, потомки A[1] = 3 и A[2] = 2. Меньший из них 2. Условие 5 > 2 выполняется, обмениваем: [2, 3, 5, 7, 9, 8].
4. Значение на индексе 2, левый потомок A[5] = 8, правого нет: индекс 6 вышел за размер кучи. Условие 5 > 8 ложно, останавливаемся.
5. Итог: [2, 3, 5, 7, 9, 8]. Возвращаем 1.

Просеивание вниз проходит не больше высоты дерева, а высота кучи из n элементов равна Θ(log n), поэтому извлечение минимума стоит O(log n). Перенос последнего элемента в корень занимает O(1), а уменьшение размера не требует сдвига данных.

Как выбрать потомка для обмена

В min-heap обмениваться нужно с меньшим из двух потомков. Допустим, корень 5 сравнивают с левым потомком 3 и правым 2, а меняют местами с 3. Тогда под узлом 3 останется узел 2, и условие 3 <= 2 нарушится сразу. Обмен с меньшим потомком гарантирует, что новое значение родителя не превышает ни одного из детей.

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

Сложность операций и сравнение с альтернативами

Отсортированный массив отдаёт минимум так же быстро, но каждая вставка требует сдвига элементов. Несортированный массив дёшево принимает новые значения, зато поиск минимума занимает O(n). Дерево поиска умеет всё за O(log n), однако на каждый узел тратит указатели и требует балансировки. Куча выигрывает в сценарии «много вставок, часто нужен только экстремум».

Почему построение кучи за O(n), а не O(n log n)

Наивный способ собрать кучу: добавлять элементы по одному, каждый раз запуская sift-up от добавленного элемента. Такой алгоритм построения работает за O(n log n), что в большинстве случаев достаточно быстро, но не оптимально. Оптимальный способ другой: взять произвольный массив и вызвать sift-down для всех индексов от n/2 - 1 до 0. Первая половина массива состоит из листьев, просеивать их незачем.

Оценка суммы: узел на высоте h просеивается максимум на h шагов, а узлов на высоте h не больше ceil(n / 2^(h+1)). Сумма n/4 * 1 + n/8 * 2 + n/16 * 3 + ... сходится к O(n). Интуиция простая: узлов вблизи листьев много, но просеиваются они на малую глубину, а глубоко просеиваются единицы. На собеседовании ответ «n вставок» по этой задаче считается ошибкой.

Когда куча в массиве - не лучший выбор

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

Если нужны поиск, вставка и удаление по ключу, берите сбалансированное дерево поиска или хеш-таблицу. Куча выигрывает там, где важен только экстремум: приоритетная очередь, планировщик, выбор следующей задачи с наивысшим приоритетом.

Типичные ошибки при реализации кучи в массиве

1. Смешивание индексации с 0 и с 1. Формулы parent = i / 2 и left = 2 * i + 1 из разных схем дают дерево, которое выглядит правдоподобно, но не соответствует массиву. Все дальнейшие проверки обманывают.
2. Выход за границы массива. Обращение к A[2 * i + 2] без проверки индекса даёт исключение или чтение чужой памяти. Сначала сравнивайте индекс с size, потом читайте значение.
3. Обмен с большим потомком в min-heap. Свойство кучи нарушается в поддереве, которое вы не проверяете, и ошибка всплывает позже, обычно на извлечении.
4. Пропущенный обмен при sift-up. Если сравнивать значения, но забыть поменять элементы местами, цикл либо завершится слишком рано, либо зависнет.
5. Неверное условие остановки. Сравнение элемента с самим собой или знак > вместо >= на равных значениях приводит к лишним обменам и лишним итерациям.
6. Потеря последнего элемента при извлечении. Порядок действий важен: сначала скопировать A[0], затем перенести A[size - 1] в корень, и только потом уменьшить size. Если уменьшить size раньше, последний элемент затрётся.
7. Извлечение из пустой кучи. Проверка size == 0 в начале pop и peek обязательна, иначе корень читается из несуществующего элемента, а size уходит в минус.

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

Индексация с 0 vs с 1: как не запутаться

В языках с массивами от нуля (C, Python, Go, Java, C++) естественнее индексация с нуля: она совпадает с нумерацией ячеек и не требует сдвига. В учебниках часто используют нумерацию с единицы, потому что формулы parent = i / 2 и left = 2 * i выглядят короче. Выбирайте одну схему и придерживайтесь её во всём коде и во всех тестах.

Проверка для индексации с нуля: для i = 1 родитель 0, потомки 3 и 4; для i = 2 родитель 0, потомки 5 и 6. Верхняя половина массива от n/2 до n - 1 состоит из листьев, потомков у них нет по определению.

Проверка границ при sift-down

Три случая нужно различать до любого сравнения: потомков нет, есть только левый потомок, есть оба. Пусть n - текущий размер кучи, тогда левый потомок существует при 2 * i + 1 < n, правый при 2 * i + 2 < n.

sift_down(A, n, i):
  while true:
    l = 2 * i + 1
    r = 2 * i + 2
    m = i
    if l < n and A[l] < A[m]: m = l
    if r < n and A[r] < A[m]: m = r
    if m == i: break
    swap(A[i], A[m])
    i = m

Сравнение с A[m] идёт после проверки границы, поэтому чтения за пределами массива не происходит. Переменная m накапливает индекс минимального из трёх значений: текущего узла и существующих потомков. Условие m == i означает, что обмен не нужен, и цикл завершается.

Практические сценарии и подготовка к собеседованию

Приоритетная очередь на куче встречается в планировщиках задач, обработчиках событий с приоритетами, алгоритме Дейкстры и таймерах внутри event loop. В инфраструктурных задачах та же структура описывает очередь сборки в CI/CD, где срочные пайплайны обгоняют фоновые, а также выбор следующего узла для балансировки с учётом веса. Смежный способ организации очередей на массиве разбираем в статье Кольцевой буфер: реализация в массиве с перезаписью для потоковой обработки.

Кучная сортировка использует ту же механику: сначала массив превращают в кучу за O(n), затем n раз извлекают минимум. Heapsort работает за O(n log n) во всех случаях и сортирует на месте, используя O(1) дополнительной памяти, но не является устойчивой сортировкой. Куча при этом не занимает места помимо самого массива: массив интерпретируется как куча, а связи родителя и потомков задаются арифметикой над индексами.

Вопросы на собеседовании по куче

1. Почему куча в массиве обходится без ссылок? Структуру полного двоичного дерева полностью задают индексы: родитель и потомки вычисляются формулами.
2. Какова сложность вставки и извлечения минимума? Обе операции O(log n), просеивание проходит не больше высоты дерева.
3. Можно ли найти произвольный элемент за O(log n)? Нет, полного порядка в куче нет, поиск занимает O(n).
4. Как построить кучу за O(n)? Вызвать sift-down для индексов от n/2 - 1 до 0. Большинство узлов находятся у листьев и просеиваются на малую глубину.
5. Чем min-heap отличается от max-heap? Направлением сравнения: в min-heap родитель не больше потомков, в max-heap не меньше.
6. Что будет, если в min-heap обменяться с большим потомком? Нарушится связь с меньшим потомком, и свойство кучи сломается в непроверенном поддереве.
7. Сколько памяти нужно для кучи из n элементов? Ровно n ячеек массива, если не считать служебных полей вроде size.

Мини-проект: приоритетная очередь на куче

Соберите класс PriorityQueue с методами push, pop, peek и size. Внутри держите массив и целое поле size, push заканчивайте вызовом sift-up, pop начинайте с переноса последнего элемента в корень и завершайте sift-down.

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

Готовые кучи есть в стандартных библиотеках. В Python это модуль heapq - реализация алгоритма очереди с кучей, также известного как алгоритм очереди с приоритетами. Наличие PriorityQueue в Java и container/heap в Go в проверенных источниках не подтверждено, поэтому перед использованием сверьтесь с официальной документацией вашей версии языка. Изучать внутреннее устройство библиотечных куч всё равно полезно: на собеседованиях просят написать просеивание по памяти, а при отладке помогает понимание, что push и pop меняют порядок элементов внутри массива целиком.

Возьмите свой рабочий язык и напишите sift-up и sift-down заново, без подсказок. Прогоните тесты, затем сравните с библиотечной версией по числу обменов на случайных данных: расхождение в разы обычно указывает на лишние обмены или неверное условие остановки.

Источники

• Двоичная куча — Викиконспекты
• Двоичная куча — Алгоритмика
• Высота полного бинарного дерева (или кучи) с N узлами
• Binary Tree Height — Stack Overflow
• Floor division with negative number — Stack Overflow
• Floor Division in Python — GeeksforGeeks
• HeapSort Algorithm: How It Works — Interview Cake
• Heapsort — Wikipedia
• heapq — Heap queue algorithm — Python documentation