Слияние двух очередей: где двоичная куча упирается

Коротко

Две кучи по n элементов слить в одну двоичная куча может только пересборкой - O(n). Причина структурная: массив требует, чтобы дерево было ПОЛНЫМ, а два полных дерева не склеиваются в одно полное без переукладки всех элементов. Значит, чтобы слияние стало дешёвым, надо отказаться от одного дерева в массиве и перейти к ЛЕСУ маленьких деревьев на указателях: тогда слияние - это объединение двух списков корней, и работы в нём O(log n), а не O(n). Так устроены биномиальная куча и куча Фибоначчи. Цена: указатели вместо арифметики, потеря кеш-дружелюбности и более сложный код - платить её стоит только тогда, когда слияния или уменьшения ключа действительно есть.

Если ты понимаешь, почему массивная куча не сливается дешевле, чем за O(n), и почему лес деревьев это чинит, листай до «Теперь сам».

Как думаешь, во сколько обойдётся слить две кучи

Есть две очереди с приоритетами, по миллиону элементов каждая, и их надо объединить в одну. Прежде чем читать дальше, прикинь стоимость двух очевидных способов на двоичной куче. Первый: вынимать элементы из второй кучи и вставлять в первую - n операций по O(log n), итого Θ(n·log n). Второй: сцепить два массива и построить кучу заново - O(n), уже лучше. Вопрос: а можно ли принципиально дешевле - за O(log n)? И если нет, то что именно мешает?

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

Два склада, где товар разложен по одному строгому правилу: ряды заполняются по порядку, без дыр, и последний ряд - только слева направо. Объединить такие склады нельзя, просто поставив один рядом с другим: у каждого свой недозаполненный последний ряд, и вместе они правило нарушают. Придётся перетаскивать коробки, пока укладка снова не станет правильной, - а это работа, пропорциональная числу коробок. Если же товар лежит не одним монолитом, а отдельными ПАЛЛЕТАМИ, объединение склада - это просто общий список паллет. Никто ничего не перекладывает.

Механизм: почему массив мешает, а лес помогает

Двоичная куча жёстко связана условием: дерево полное, поэтому индексы считаются арифметикой, а память - один непрерывный массив. Слить две такие кучи - значит получить новое полное дерево из 2n узлов. Взять корни и подвесить одно дерево к другому нельзя: результат перестанет быть полным (у корня окажется поддерево нужной формы только в одном случае из многих), и арифметика индексов сломается. Остаётся переукладка - Θ(n).

Выход в том, чтобы разрешить структуре быть НЕСКОЛЬКИМИ деревьями:

двоичная куча   : одно полное дерево в массиве
                  слияние = пересборка               O(n)

лес деревьев    : несколько деревьев на указателях,
                  у каждого своё свойство кучи
                  слияние = объединить списки корней O(log n) или даже O(1)
                  минимум = лучший из корней

Сразу возникает вопрос, который и определяет конструкцию: если деревьев много, то где минимум и сколько стоит его найти? Ответ - в одном из корней, и чтобы перебор корней был дешёвым, число деревьев надо держать небольшим: O(log n). Отсюда два разных ответа, которые и составляют следующие два урока. Биномиальная куча держит порядок строго: размеры деревьев - степени двойки, по одному дереву на единицу в двоичной записи n, слияние работает как сложение двоичных чисел. Куча Фибоначчи наводит порядок ЛЕНИВО: слияние просто сцепляет списки за O(1), а разбор завалов откладывается до извлечения минимума.

Одно полное дерево в массиве не склеивается с другим без переукладки. Лес маленьких деревьев на указателях сливается объединением списка корней - платим за это поиском минимума среди корней.

Правило

Две двоичные кучи СОПОСТАВИМОГО размера не сливаются дешевле O(n): требование «дерево полное, уложено в массив» не допускает склейки без переукладки. (Влить маленькую кучу в большую дешевле - это O(k·log n) вставок, и на этом стоит приём «малое к большому»; речь именно про две кучи по n элементов.) Дешёвое слияние требует ЛЕСА деревьев на указателях - тогда слияние это объединение списков корней (O(log n) у биномиальной кучи, O(1) у кучи Фибоначчи), а минимум ищется среди корней, поэтому число деревьев держат в O(log n). Плата - указатели вместо арифметики индексов, память на узел и потеря кеш-дружелюбности.

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

Считаем на n = 10⁶ в каждой куче, log₂ 10⁶ ≈ 20.

Переливание по одному. pop из второй кучи плюс push в первую: 10⁶ пар операций по O(log n) - порядка 2·10⁶·20 = 40 миллионов элементарных шагов. Хуже всех, а пишут чаще всего, потому что не задумываются.
Пересборка. Сцепить массивы (2·10⁶ копирований) и построить кучу за O(n) - порядка 4·10⁶ шагов, в десять раз меньше. Это потолок для массивной кучи, и он линеен.
Лес деревьев. Объединить списки корней: у биномиальной кучи это O(log n) - порядка двадцати шагов. Разница с пересборкой - не в разы, а в двести тысяч раз.

Вывод, который стоит унести из этих чисел: если слияний в задаче НЕТ, разница неважна, а сложная структура только мешает. Если слияния идут в цикле (объединяем тысячи очередей), разрыв между O(n) и O(log n) определяет, работает решение или нет.

Разбор: где слияния возникают на самом деле

Слияние очередей звучит экзотикой, пока не посмотреть, откуда оно берётся. Первое: алгоритмы на графах, которые объединяют компоненты. В алгоритме Борувки компоненты сливаются парами на каждой фазе, и вместе с ними - их очереди исходящих рёбер. Второе: поиск k кратчайших путей и подобные задачи, где к частичному решению приклеивают целую очередь кандидатов. Третье: объединение результатов параллельных задач - каждый поток собрал свою очередь топ-кандидатов, в конце их надо свести. Четвёртое: оффлайн-обработка деревьев приёмом «малое к большому», где на каждом узле сливают структуры детей; там слияние - основная операция, и её цена определяет всё.

И честная оговорка. Во многих из этих задач можно обойтись без сливаемых куч: в «малом к большому» переливают меньшую структуру в большую и получают O(n·log²n) без всяких биномиальных деревьев, а в Борувке очереди можно строить заново на каждой фазе. Сливаемая куча - это инструмент, превращающий log² в log или линию в логарифм; она нужна там, где такой разницы хватает, чтобы задача уложилась в срок. Не наоборот - не «есть красивая структура, найдём ей применение».

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

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

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

Прямая практическая польза этого урока - умение распознать, что задача упирается именно в слияние, и не лечить это переливанием. Но главная польза шире: здесь видно, как ОГРАНИЧЕНИЕ ФОРМЫ оборачивается ограничением операций. Двоичная куча быстра и компактна ровно потому, что жёстко держит форму полного дерева, - и по той же причине не умеет сливаться. Хочешь другую операцию - ослабь форму: разреши несколько деревьев, разреши временный беспорядок, откладывай уборку. Это общий приём проектирования структур, и он встретится ещё не раз: B-дерево ослабляет двоичность ради диска, splay-дерево отказывается от инварианта баланса ради амортизации, хеш-таблица отказывается от порядка ради константы. Каждый раз вопрос один: какое свойство я готов отпустить и что получу взамен.

Теперь сам

Нужно свести 1000 очередей по 1000 элементов в одну. Посчитай порядок работы для двух способов: (а) последовательная пересборка (слили первые две, к результату добавили третью и так далее), (б) слияние лесов за O(log n) на операцию.

Ответ. (а) Пересборка стоит O(размера результата). После i-го слияния в куче 1000·(i+1) элементов, и каждое слияние стоит примерно столько же. Суммируем: 1000·(2 + 3 + ... + 1000) ≈ 1000 · 500000 = 5·10⁸ шагов - полмиллиарда, и это при том, что элементов всего миллион. Причина знакомая: повторная работа, каждый раз переукладываем весь накопленный результат. Кстати, если сливать не цепочкой, а ПАРАМИ (турниром: 500 слияний по 2000, потом 250 по 4000 и так далее), та же пересборка даст 10⁶·log₂ 1000 ≈ 10⁷ - в пятьдесят раз лучше, и это стоит помнить отдельно: часто дело не в структуре, а в порядке операций. (б) Слияние лесов: 999 слияний по O(log 10⁶) ≈ 20 шагов - около 20 тысяч шагов на всё, плюс сами вставки элементов. Разрыв с наивной цепочкой - четыре порядка. Заметь, что ответ на вопрос «нужна ли мне сливаемая куча» зависит не только от структуры, но и от того, догадался ли ты сливать турниром.

Главное

Двоичная куча не умеет дешёвого слияния двух куч СОПОСТАВИМОГО размера и не может уметь: она держит форму полного дерева, чтобы жить в массиве, а два полных дерева не склеиваются в одно без переукладки всех элементов - Θ(n). (Влить маленькую в большую можно и дешевле - k вставок.) Чтобы слияние стало логарифмическим, структуру ослабляют: вместо одного дерева в массиве - ЛЕС маленьких деревьев на указателях, и слияние превращается в объединение списков корней. Минимум при этом живёт в одном из корней, поэтому число деревьев приходится держать в O(log n) - отсюда конструкции следующих уроков: биномиальная куча наводит порядок сразу (размеры деревьев - степени двойки, слияние как сложение в двоичной системе), куча Фибоначчи - лениво (сцепить за O(1), прибраться при извлечении). Плата за слияние - указатели, память на узел и промахи кеша, поэтому берут такие кучи только там, где слияния или уменьшения ключа действительно есть. И общий приём на будущее: новая операция покупается ослаблением формы.