Двоичная куча: дерево, которое живёт в массиве

Коротко

Двоичная куча - это почти полное двоичное дерево со свойством кучи: в макс-куче родитель не меньше своих детей (значит на вершине - максимум). Дерево не хранят ссылками - его укладывают в обычный МАССИВ: у элемента с индексом i дети лежат на 2i+1 и 2i+2, а родитель - на (i−1)//2. Главная операция - просеивание вниз (sift-down): если элемент меньше ребёнка, меняем его с бо́льшим ребёнком и повторяем, пока свойство кучи не восстановится. Один спуск - O(log n) (высота дерева). На куче стоят и пирамидальная сортировка, и очередь с приоритетом.

Если ты знаешь свойство кучи, как куча укладывается в массив (дети 2i+1, 2i+2; родитель (i−1)//2) и как работает просеивание вниз за O(log n), листай до «Теперь сам».

Как думаешь, как быстро доставать максимум снова и снова

Пусть надо много раз доставать самый большой элемент и добавлять новые. Держать массив отсортированным дорого (вставка O(n)). Держать неотсортированным - дорог поиск максимума (O(n) каждый раз). Нужна структура посередине: не полный порядок, а ровно столько порядка, чтобы максимум был под рукой, а вставка и удаление стоили дёшево. Такой компромисс и даёт куча: максимум всегда на вершине (O(1) посмотреть), а поправить кучу после изменения - O(log n).

На что это похоже

Турнирная пирамида: наверху - чемпион, ниже - те, кого он обыграл, ещё ниже - их жертвы. Точного места у всех нет (второй и третий могут стоять как угодно между собой), но одно правило соблюдается железно: любой стоит НЕ ВЫШЕ того, кто его победил. Поэтому чемпион гарантированно наверху - искать не надо. Когда чемпион уходит, на его место поднимают сильнейшего из нижних, и пирамида быстро перестраивается, а не пересобирается с нуля.

Механизм: свойство кучи, укладка в массив, просеивание

Свойство кучи (макс-куча): для каждого узла его значение ≥ значений его детей. Отсюда максимум всего дерева - в корне. Дерево «почти полное»: заполнено по уровням слева направо, без дыр.

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

Куча - это дерево, но хранится оно в массиве: связи между узлами вычисляются по индексу, а не по ссылкам.

Просеивание вниз (sift-down). Если узел нарушил свойство (стал меньше ребёнка): сравниваем его с бо́льшим из детей и, если узел меньше, меняем их местами; теперь узел опустился на уровень - повторяем на новом месте, пока он не станет ≥ детей или не дойдёт до листа. Спуск идёт по высоте дерева - O(log n).

Правило

Двоичная куча - почти полное двоичное дерево со свойством: родитель ≥ детей (макс-куча), поэтому максимум в корне. Хранится в массиве: у узла i дети 2i+1, 2i+2, родитель (i−1)//2 - без ссылок. Просеивание вниз восстанавливает свойство, опуская нарушивший узел по высоте дерева за O(log n). Куча даёт максимум за O(1), а вставку и удаление максимума - за O(log n).

Разбор: почему формулы индексов работают

Пронумеруем узлы по уровням слева направо, начиная с 0. Корень - 0. На уровне k лежат узлы, на следующем их вдвое больше. Если узел i, то его левый ребёнок оказывается на позиции 2i+1, правый - 2i+2 (проверь на дереве выше: у корня 0 дети 1 и 2; у узла 1 дети 3 и 4; у узла 2 дети 5 и ...). Обратная формула: родитель узла i - это (i−1)//2 (у 3 и 4 родитель 1; у 5 и 6 - 2). Всё это работает ТОЛЬКО потому, что дерево почти полное (заполнено по уровням без дыр) - иначе индексы разъехались бы. Именно компактная укладка без ссылок делает кучу такой дешёвой по памяти и быстрой: переход к ребёнку или родителю - одно арифметическое действие.

Разбор: почему один спуск - это O(log n)

Просеивание вниз на каждом шаге опускает узел на ОДИН уровень. Уровней в почти полном двоичном дереве из n узлов - ⌊log₂ n⌋ + 1 (каждый уровень вмещает вдвое больше предыдущего, поэтому чтобы набрать n узлов, уровней нужно порядка log₂ n). Значит спуск делает не больше log₂ n шагов, на каждом - пара сравнений с детьми и, может быть, обмен: O(log n). Та же логика у просеивания ВВЕРХ (когда добавляют новый элемент в конец и поднимают его к корню, пока он больше родителя) - тоже O(log n). Логарифм здесь ровно потому, что дерево двоичное: его высота логарифмична от числа узлов, как у двоичного поиска.

Что ломается без этого

Первая ошибка - перепутать формулы индексов (например, взять родителя как i//2 вместо (i−1)//2): переходы «промахиваются» мимо нужных узлов, и куча ломается молча - массив на вид цел, а свойство кучи нарушено. Вторая - при просеивании вниз менять узел с ЛЮБЫМ ребёнком, а не с БОЛЬШИМ: тогда наверх может подняться не максимум, и свойство кучи не восстановится. Третья - забыть, что куча - это НЕ отсортированный массив: она гарантирует только максимум в корне, а порядок остальных элементов произволен (в примере выше 7 и 8 стоят «не по порядку» - и это нормально).

Зачем это в работе

Куча - это реализация очереди с приоритетом: структуры, из которой всегда достаётся самый важный элемент. На ней стоят планировщики задач (взять задачу с наивысшим приоритетом), алгоритм Дейкстры (взять ближайшую вершину), сжатие Хаффмана (взять два наименьших веса), слияние k отсортированных потоков. Во всех них нужно многократно доставать экстремум и добавлять новые элементы - ровно то, что куча делает за O(log n) вместо O(n). В стандартных библиотеках это heapq в Python, PriorityQueue в Java. А в этой главе на куче мы построим сортировку - пирамидальную, которая сортирует на месте и гарантирует n·log n.

Теперь сам

В массиве-куче [9, 7, 8, 3, 5, 6] какие индексы у детей узла 1 (значение 7) и кто его родитель? И почему то, что 7 меньше 8 (узла 2), НЕ нарушает свойство кучи?

Ответ. У узла 1 дети на 2·1+1 = 3 и 2·1+2 = 4 - это значения 3 и 5; родитель узла 1 - это (1−1)//2 = 0, то есть корень 9. Свойство кучи проверяется только между РОДИТЕЛЕМ и его ДЕТЬМИ, а не между произвольными узлами. 7 (узел 1) и 8 (узел 2) - не родитель и ребёнок, а «братья»-соседи под общим родителем 9; их взаимный порядок свойство кучи не регулирует. Важно лишь, что 7 ≥ 3 и 7 ≥ 5 (свои дети) и что 9 ≥ 7 и 9 ≥ 8. Всё соблюдено - куча корректна, хотя 7 и 8 стоят «не по росту».

Главное

Двоичная куча - почти полное двоичное дерево со свойством: родитель ≥ детей (макс-куча), поэтому максимум в корне. Хранится в МАССИВЕ без ссылок: у узла i дети 2i+1 и 2i+2, родитель (i−1)//2 (работает благодаря заполнению по уровням без дыр). Просеивание вниз восстанавливает свойство, опуская узел на один уровень за шаг, - O(log n) (высота двоичного дерева). Свойство связывает лишь родителя с детьми, братья не упорядочены - куча это не отсортированный массив. На ней стоят очередь с приоритетом и пирамидальная сортировка.