Кучи с эффективным слиянием

В статье про двоичную кучу было рассказано про устройство такой структуры данных как куча, а также приведён пример реализации в виде двоичной кучи. Такая реализация обладает двумя бесспорными преимуществами: простотой и компактностью хранения. Однако одна операция, часто требуемая от кучи в ней имеет слишком высокую сложность, эта операция слияние (meld). По сути лучшим способом слияния двоичных куч является построение новой кучи на объединённом массиве элементов. Сложность такой операции будет \(O(n + m)\) или, если одна из сливаемых куч сильно меньше другой, то можно поэлементно добавить первую ко второй, получив сложность \(O(n \log m)\).

Деревья, рассматриваемые в этой статье не отличаются простотой и компактностью, однако, оптимизированы для выполнения операции объединения. Собственно все операции в этих структурах сводятся к операции объединения.

Биномиальные кучи¹

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

Биномиальное дерево

Самый простой способ определения того что из себя представляет биномиальное дерево является рекурентный. Биномиальное дерево порядка \(0\) состоит из одной вершины, а биномиальное дерево порядка \(k\) является объединением двух деревьев порядка \(k - 1\) так, что корень одного из них является сыном корня другого. Из этого определения очевидно, что количество элементов в биномиальном дереве порядка \(k\) равно \(2^k\). Вот как будут выглядеть несколько первых биномиальных деревьев:

«Несложно» догадаться, что название «биномиальные» эти деревья получили от того, что количество вершин по уровням представляет из себя биномиальные последовательности, например, для \(k = 5\) биномиальная последовательность равна \((1, 5, 10, 10, 5, 1)\)

Также несложно видеть, что высота такого дерева будет \(k + 1\).

Адресация в биномиальном дереве

С формой всё вроде понятно, но как хранить такое дерево? Вообще хранить деревья с переменной степенью ветвления та ещё морока, но есть более или менее универсальный способ, не зависящий от формы дерева вообще. Но, прежде чем перейти к нему, заметим, что вообще биномиальное дерево вполне отлично хранится в обычном массиве, при этом для нисхождения по дереву адресация будет однозначной.

Пусть корень хранится в нулевом элементе и для \(i\)-го элемента его дети имеют индексы \(i + 2^j\), где \(j < k_i\) степени ветвления вершины \(i\). Получаем примерно следующую картину:

Также несложно видеть, что у корня будет \(k\) сыновей, а у сына \(i\)-го элемента с индексом \(i + 2^j\) будет \(j\) сыновей. Таким образом легко спускаться по дереву, хотя чистый спуск требуется редко, разве что для операции увеличения ключа. При этом способ узнать родителя элемента не такой очевидный (?).

Но это хорошо, до тех пор, пока такое дерево не меняется, потому как при любом изменении возможно выделение памяти и копирование данных. Так что сложность изменения может быть равно \(O(n)\).

Вместо этого воспользуемся так называемым LCRS-деревом². Эта аббревиатура расшифровывается как Left-Child, Right-Sibling, то есть каждый элемент хранит два указателя: на левого сына и следующего брата. Получается следующая картина:

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

Получатся зацикленные списки, по которым можно будет свободно обходить всё дерево (?).

Слияние биномиальных деревьев

Биномиальные деревья сливаются по определению, то есть

Биномиальное дерево порядка \(k\) является объединением двух деревьев порядка \(k - 1\) так, что корень одного из них является сыном корня другого.

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

Биномиальный лес

Если в количество элементов в куче не является степенью двойки, тогда их надо разделить на нужное число биномиальных деревьев разной высоты. Например, возьмём \(13\) элементов:

Число \(13\) представимо в виде \(1 + 4 + 8 = 2^0 + 2^2 + 2^3\). То есть элементы этого множества можно распределить по биномиальным деревьям порядков \(0\), \(2\) и \(3\).

Осталось только переставить элементы в деревьях так, чтобы они удовлетворяли условию кучи, и вуаля!

Определим на таких лесах операцию meld. Для этого будем сливать деревья одного порядка от младшего к старшему с переносом. Для примера сольём наш лес со следующим:

Младшими в обоих лесах оказываются деревья порядка \(0\). Сливаем их, сохраняя свойство кучи.

Получилось дерево порядка \(1\). Но второй лес также содержит дерево этого порядка, так что надо слить и их тоже, получив дерево порядка \(2\).

При этом первый лес также содержит дерево порядка \(2\). Сольём и их.

Наконец, первый лес также содержит дерево порядка \(3\), сольём и их, получив одно дерево как итоговый лес.

Несложно увидеть, что итоговый набор куч можно получить сложив количества элементов в двоичной записи:

Также легко заметить, что количество деревьев в куче, состоящей из \(n\) элементов, будет не больше чем \(\lfloor 1 + \log n \rfloor\). К сожалению, минимум всего леса может быть корнем любого из деревьев. Для оптимизации метода peek лучше хранить номер дерева, содержащего глобальный минимум, обновляя его по мере изменения леса.

Вставка и извлечение минимума

Операцию вставки можно свести к слиянию текущего леса с лесом, состоящим из одного дерева порядка \(0\). При извлечении же минимума дерево, которое его содержало разделяется на деревья меньших порядков. Для примера извлечём минимум из дерева, получившегося в предыдущем параграфе. После удаления корня получим следующий лес:

Если бы лес содержал другие деревья, то необходимо было бы выполнить операцию слияния оставшихся деревьев с этим новым лесом.

Оценка сложности

Заметим, что слияние двух деревьев операция константной сложности:

• выбрать минимум из двух корней;
• назначить меньший корень родителем большего;

С другой стороны сложность слияния двух лесов может вылиться к попарному слиянию деревьев. Так как в лесе из \(n\) элементов не более \(\lfloor 1 + \log n \rfloor\) деревьев, получаем, что сложность слияния лесов, состоящих из \(n\) и \(m\) элементов, будет иметь сложность \(O(\log \max (n, m))\). Таким образом сложность вставки и извлечения минимума будет \(O(\log n)\), однако, несложно доказать, что учётная стоимость вставки будет \(O(1)\) (?).

Левацкие кучи³

Левацкие кучи в отличии от биномиальных являются деревьями, причём двоичными, но не полными. Для определения левацких куч нам потребуются дополнительные определения.

Рангом вершины будем называть высоту полного двоичного поддерева с корнем в этой вершине. Для большей формальности определим ранг следующим образом:

Дерево будем называть левацким, если в любой его вершине ранг левого сына не меньше ранга правого сына.

Несложно видеть, что для любой непустой вершины \(v\) в левацкой куче выполняется равенство \(r(v) = 1 + r(v_r)\). Также из определения следует, что в дереве, ранг которого равен \(k\) не меньше, чем \(2^k\) элементов. То есть ранг дерева из \(n\) элементов не превосходит \(\log n\). Из этого следует, что длинна правого пути в таком дереве не будет превосходить \(\log n\). Вообще для простоты будем изображать левацкие деревья следующим образом:

Потому как нас будет интересовать в них только правый путь. Также будем обозначать через \(x(A, B)\) дерево с корнем в вершине \(x\) с двумя поддеревьями: \(A\) и \(B\), левым и правым соответственно.

Добавим к свойствам левацкости свойство кучи и получим левацкую кучу. Для него определим операцию слияния следующим рекурентным образом:

Рассмотрим слияние двух левацких куч:

В результате рекурсивного применения операции слияния мы получим следующее дерево:

Сложность такой операции будет \(O(r(A) + r(B)) = O(\log n)\), но можно оптимизировать, так как по сути это слияние двух отсортированных списков. Но есть одна проблема: получившееся дерево, хоть и является кучей, но скорее всего не левацкое. Для того, чтобы вернуть ему необходимые свойства, надо пройтись по правому пути обратно и для вершин, в которых нарушаются свойства левацкости поменять сыновей местами. Таким образом удобнее всего здесь использовать стек и рекурсивные вызовы, а обмены оставить на выход из рекурсии, что, конечно, сделает невозможным оптимизацию хвостовой рекурсии.

Также операция decrease_key не является эффективной на левацких кучах: левые пути могут быть сколь угодно длинным, вплоть до того, что если взять дерево, в котором есть только левый путь, оно тоже будет левацким. Таким образом сложность операции decrease_key ограничено лишь \(O(n)\).

Косые кучи⁴

В структуре левацкой кучи всё хорошо, кроме одного момента: дополнительные данные. Рядом с каждой вершиной мы должны хранить её ранг. По факту он нам требуется только для выхода из рекурсии для разворота некоторых вершин, но вычислять его на ходу слишком дорого, так что приходится хранить. Косые (skew) кучи исправляют этот недостаток. Вместо того, чтобы хранить ранги вершин, просто будем разворачивать все вершины правого пути (а заодно можно и хвостовую рекурсию оптимизировать). Несмотря на то, что косая куча не являются левацкой, она также имеет логарифмическую оценку сложности слияния, правда учётную. Давайте докажем эту оценку.

Для оценки будем использовать банковский метод, также известный как метод предоплаты, то есть определим некоторую константу \(c\), такую что, количество базовых операций требуемых для слияния будет ограничено сверху \(c\log n\), где \(n\) — величина результата слияния. Излишек мы будем располагать на нашей структуре как предоплату для будущих операций. Осталось определиться с величиной \(c\) и тем — где хранить предоплату. Для этого введём дополнительные определения.

Весом вершины (\(\leftrightharpoons \operatorname{w}(v)\)) будем называть количество вершин в дереве с корнем в этой вершине. Будем говорить, что вершина тяжёлая, если её вес не меньше половины веса её родителя. Заметим, что тяжёлым может быть только один сын, при этом может быть, что обы сына не являются тяжёлыми. Наконец, будем говорить, что вершина плохая, если она тяжёлая и при этом является правым сыном.

Легко понять, что в любой пути от корня до листа дерева не более, чем \(\log n\) не тяжёлых вершин. Действительно, каждый раз при переходе в лёгкую вершину остаток вершин под ней не менее чем уполовинивается. Если же путь превышает по длине \(\log n\), это означает, что в нём есть тяжёлые вершины. Таким образом, правый путь состоит из \(\log n\) хороших вершин, остальные плохие.

Именно в плохих вершинах и будем накапливать предоплату. Так как на плохих вершинах лежат монетки, их слияние и разворот предоплачен. Но после процедуры слияния и разворота необходимо разложить новую предоплату на новые плохие вершины. Собственно плохие вершины могут образоваться в корнях деревьев \(A_i\) и \(B_j\), ведь мы сделали обмен сыновей во всех вершинах правого пути так, что он стал левым.

Но, если корень дерева \(A_i\) или \(B_j\) оказывается плохой вершиной, значит это тяжёлый правый сын, а значит левый сын — лёгкий, а как мы показали выше: в любом пути не более чем \(\log n\) лёгких вершин. Таким образом плохих вершин образуется не более чем \(\log n\). Итого, если брать по 1 монете за операцию слияния и разворота, то на процедуру слияния нам потребуется не более чем \(2 \log n\) монет: \(\log n\) на слияние лёгких вершин правого пути, тяжёлые уже содержат на себе монету предоплаты, и ещё \(\log n\) на предоплату вновь образованных плохих вершин.

Рандомизированные кучи⁵

Ещё один вариант куч с эффективным слиянием являются рандомизированные куч. Процедура слияния в них работают также как в косых или левацких, но не по правому пути, а по случайному пути: на каждый раз мы случайным образом выбираем в каком из сыновей продолжить слияние. Математическое ожидание длинны любого пути от корня до листа в таком дереве равно \(\log n\), при этом в большинстве случаев оно не превышает \(2 \log n\). Это называется рандомизированный логарифм и о нём более подробно будет рассказываться в рандомизированных деревьях поиска. Здесь лишь отметим, что в рандомизированных кучах операция decrease_key также является эффективной.

Вопросы

1. ^ Как определить индекс родителя при хранении биномиального дерева в массиве, описанным способом?
2. ^ Какова будет сложность обхода всего LCRS-дерева, например, если необходимо посчитать сумму всех его вершин? Какая максимальная сложность будет при переходе от вершины к вершине?
3. ^ Докажите, что учётная стоимость вставки в биномиальную кучу составляет \(O(1)\).
4. * Является ли эффективной операция decrease_key для косых куч? Можно ли получить учётную оценку её стоимости?

Дополнительное чтение