Построение кучи за линию

Коротко

Собрать кучу из готового массива можно за Θ(n) - линейно, а не за Θ(n·log n). Приём: идти по узлам СНИЗУ ВВЕРХ (от последнего родителя к корню) и для каждого делать просеивание вниз. Кажется, что раз просеивание стоит O(log n), а узлов n, то всё - O(n·log n). Но это завышение: почти все узлы - у самого низа дерева, где просеивать почти некуда (высота 0-1), и лишь редкие верхние узлы стоят дорого. Точный подсчёт даёт сумму n · Σ h/2ʰ, а этот ряд сходится к константе - значит построение Θ(n).

Если ты знаешь, что куча строится за Θ(n) просеиванием снизу вверх, и понимаешь, почему это Θ(n), а не Θ(n·log n) (ряд Σ h/2ʰ сходится), листай до «Теперь сам».

Как думаешь, во сколько обходится собрать кучу из массива

Есть произвольный массив, надо сделать из него кучу. Прямой способ: добавлять элементы по одному, каждый раз просеивая новый вверх, - n вставок по O(log n), итого O(n·log n). Но есть способ вдвойне лучше: взять массив как есть (он уже «дерево», просто с нарушенным свойством) и починить его снизу вверх. Удивительно, но такое построение стоит всего Θ(n) - линейно. Разберём, как и почему; заодно это красивый пример, где грубая оценка O(n·log n) завышена, а точный подсчёт даёт меньше.

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

Представь, что надо навести порядок подчинения в большой компании, где связи «начальник - подчинённый» уже расставлены, но кое-где младший оказался «сильнее» старшего. Чинить разумнее СНИЗУ: сначала уладить мелкие группы у самого низа (их много, но каждая крохотная - работы на копейки), потом группы повыше (их меньше). К моменту, когда доходишь до директора, все нижние уровни уже в порядке, и его правка опирается на готовое. Основная масса народа - внизу, и там правки дешёвые; наверху правки дорогие, но таких людей единицы.

Механизм: просеивание снизу вверх

Массив уже задаёт почти полное дерево (по формулам индексов из прошлого урока). Листья (вторая половина массива, индексы от n//2 до n−1) - это уже кучи из одного элемента, их чинить не надо. Начинаем с ПОСЛЕДНЕГО НЕлиста - индекс n//2 − 1 - и идём вниз по индексам до корня 0. Для каждого узла делаем просеивание вниз: оно опускает узел, пока он не станет ≥ детей. Ключевой момент: когда мы просеиваем узел, оба его поддерева УЖЕ кучи (мы шли снизу вверх и починили их раньше) - значит одного спуска достаточно, чтобы узел встал на место.

для i от n//2 − 1 до 0:
    просеять_вниз(i)

После прохода корень содержит максимум, и всё дерево - корректная куча.

Правило

Куча строится из массива за Θ(n) просеиванием вниз по узлам СНИЗУ ВВЕРХ (от n//2 − 1 до 0). Это линейно, а не Θ(n·log n), потому что почти все узлы - у низа дерева, где просеивать почти некуда: сумма высот всех узлов есть Θ(n), а не Θ(n·log n). Листья (вторая половина массива) пропускают - они уже кучи из одного элемента.

Разбор: почему это Θ(n), а не Θ(n·log n)

Грубая оценка «n узлов × O(log n) на просеивание = O(n·log n)» верна как ВЕРХНЯЯ граница, но сильно завышена, потому что не все узлы просеиваются на всю глубину. Считаем точнее по ВЫСОТЕ узла (высота листа - 0, корня - log n). Просеивание узла высоты h стоит O(h). А сколько узлов высоты h? Не больше ⌈n / 2^(h+1)⌉ - чем выше, тем меньше (листьев - половина всех узлов, узлов высоты 1 - четверть, и так далее). Суммарная работа:

Σ (число узлов высоты h) · O(h)  ≤  n · Σ (h / 2^(h+1))  =  O(n)

потому что ряд Σ h/2ʰ = 1/2 + 2/4 + 3/8 + ... = 2 СХОДИТСЯ к константе. Значит вся работа - n умножить на константу, то есть Θ(n). Смысл прост: дорогих просеиваний (у верхних узлов) - единицы, а массовые дешёвые (у нижних) в сумме дают константу на узел. Это тот самый случай из раздела про рекуррентности, где грубое перемножение «худших» врёт, а честная сумма мала.

Разбор: почему добавлять по одному хуже

Сравни с наивным построением «добавлять по одному с просеиванием вверх». Там всё наоборот по «весам»: новый элемент садится в ЛИСТ (у самого низа) и может всплыть до корня - то есть дорогие узлы (высоко всплывающие) встречаются часто, ведь половина вставок - это листья, которым до корня далеко. Точный подсчёт для вставки по одному даёт Θ(n·log n) в худшем случае. Разница между двумя способами - в том, КУДА просеиваются элементы. Готовый способ (heapify) просеивает узлы ВНИЗ (sift-down), обходя их снизу вверх, - дёшево, потому что массовые узлы у дна опускать почти некуда; наивный способ добавляет по одному и просеивает каждый новый элемент ВВЕРХ (sift-up) - дорого, потому что массовые вставки-листья всплывают далеко. Одна и та же куча, но Θ(n) против Θ(n·log n) - направление просеивания решает.

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

Первая ошибка - строить кучу добавлением по одному и считать это оптимальным: получишь O(n·log n) там, где есть Θ(n). На больших данных это заметная потеря (и, например, делает всю подготовку к алгоритму дороже, чем нужно). Вторая - начать просеивание не с n//2 − 1, а с 0 (сверху вниз): тогда, просеивая верхний узел, ты опираешься на ещё НЕ починенные поддеревья, и куча не соберётся за один проход. Порядок обхода (снизу вверх) - не деталь, а условие корректности. Третья - забыть, что листья чинить не надо, и зря просеивать вторую половину массива (не ошибка результата, но лишняя работа).

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

Построение кучи за Θ(n) - это первый шаг пирамидальной сортировки (следующий урок): она сперва за линию строит кучу, а потом за n·log n разбирает её. Тот же приём нужен, когда очередь с приоритетом инициализируют СРАЗУ из готового набора (например, загрузили все задачи и хотим построить планировщик): heapify в Python (heapq.heapify) делает ровно это - превращает список в кучу за Θ(n), а не добавляет по одному за n·log n. Знать, что построение линейно, важно и как факт («не плати log n там, где не надо»), и как урок анализа: одинаковая на вид работа стоит по-разному в зависимости от того, где сосредоточена её масса.

Теперь сам

В дереве из n узлов примерно половина - листья, четверть - узлы высоты 1, восьмая - высоты 2 и так далее. Почему из-за этого построение кучи снизу вверх выходит Θ(n), а не Θ(n·log n)?

Ответ. Просеивание узла высоты h стоит O(h), но узлов высоты h мало - около n/2^(h+1). Дорогие просеивания (большие h) приходятся на РЕДКИЕ верхние узлы, а массовые узлы у дна (h = 0, 1) просеивать почти некуда. Складываем: n·(1/2·0 + 1/4·1 + 1/8·2 + ...), а ряд Σ h/2ʰ сходится к константе (= 2). Значит суммарная работа - n умножить на константу, то есть Θ(n). Грубая оценка n × log n завышена, потому что она приписывает КАЖДОМУ узлу глубину log n, тогда как её имеют лишь единицы у корня, а большинство узлов почти не двигаются.

Главное

Кучу строят из массива за Θ(n) просеиванием вниз по узлам СНИЗУ ВВЕРХ (от n//2 − 1 до 0); листья (вторая половина массива) уже готовы. Это линейно, а не Θ(n·log n), потому что почти все узлы - у дна дерева, где просеивать почти некуда: узлов высоты h около n/2^(h+1), и сумма n·Σ h/2ʰ = Θ(n) (ряд сходится к константе). Наивное добавление по одному (просеивание вверх) даёт Θ(n·log n), потому что массовые вставки-листья всплывают далеко. Направление просеивания решает; порядок «снизу вверх» - условие корректности.