Биномиальные и фибоначчиевы кучи

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

Для каждого $$k = 0, 1, 2, \ldots$$ биномиальное дерево $$B_k$$ определяется следующим образом: $$B_0$$ — дерево, состоящее из одного узла высоты $$0$$ ; далее при $$k = 1, 2, \ldots$$ дерево $$B_k$$ высоты $$k$$ формируется из двух деревьев $$B_{k-1}$$, при этом корень одного из них становится потомком корня другого. На рис. 7.1 изображены биномиальные деревья $$B_0, B_1, B_2, B_3, B_4$$.

Биномиальный лес — это набор биномиальных деревьев, в котором любые два дерева имеют разные высоты.

Свойства биномиальных деревьев

Чтобы убедиться в существовании биномиального леса из $$n$$ узлов, представим $$n$$ в двоичной системе счисления (разложим по степеням двойки) $$n = a_0 2^0 + a_1 2^1 + \ldots +a_s 2^s$$, где $$a_k \in \{0, 1\}$$. Для каждого $$k = 0, 1, 2 \dts s$$, такого, что $$a_k = 1$$, в искомый лес включаем дерево $$B_k$$.

Биномиальная куча — это набор биномиальных деревьев, узлам которых приписаны элементы взвешенного множества в соответствии с кучеобразным порядком, при котором вес элемента, приписанного узлу, не превосходит весов элементов, приписанных его потомкам.

Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей$$\eq*{ [{\rm key}, {\rm parent}, {\rm child}, {\rm sibling}, {\rm degree}], }$$ где $${\rm key}$$ — ключ (вес) элемента, приписанного узлу, $${\rm parent}$$ — родитель узла, $${\rm child}$$ — левый ребенок узла, $${\rm sibling}$$ — правый брат узла, $${\rm degree}$$ — степень узла.

Доступ к куче осуществляется ссылкой на самое левое поддерево. Корни деревьев, из которых составлена куча, оказываются организованными с помощью поля $${\rm sibling}$$ в так называемый корневой односвязный список.

Поиск элемента с минимальным ключом. Поскольку искомый элемент находится в корне одного из деревьев кучи, элемент с минимальным ключом находится путем просмотра корневого списка за время $$O(\log n)$$.

Слияние двух очередей. Две очереди $$H_1$$ и $$H_2$$ объединяются в одну очередь $$H$$ следующим образом. Последовательно выбираются деревья из исходных очередей в порядке возрастания их высот и вставляются в результирующую очередь $$H$$, вначале пустую.

Если дерево $$B_i$$ очередной высоты $$i$$ присутствует лишь в одной из исходных очередей, то перемещаем его в результирующую очередь. Если оно присутствует в одной из исходных очередей и уже есть в результирующей очереди, то объединяем эти деревья в одно $$B_{i+1}$$, которое вставляем в $$H$$. Если $$B_i$$ присутствует во всех трех очередях, то сливаем два из них в $$B_{i+1}$$ и вставляем в $$H$$, а третье дерево $$B_i$$ просто перемещаем в $$H$$. Трудоемкость — $$O(\log n)$$.

Вставка нового элемента. Создается одноэлементная очередь из вставляемого элемента, которая объединяется с исходной очередью. Трудоемкость — $$O(\log n)$$.

Удаление минимального элемента. Сначала в исходной куче $$H$$ производится поиск дерева $$B_k$$, имеющего корень с минимальным ключом. Найденное дерево удаляется из $$H$$, его прикорневые поддеревья $$B_{k-1}\dts B_1, B_0$$ включаются в новую очередь $$H_1$$, которая объединяется с исходной очередью $$H$$. Трудоемкость — $$O(\log n)$$.

Уменьшение ключа. Осуществляется с помощью всплытия. Трудоемкость — $$O(\log n)$$.

Удаление элемента. Уменьшается ключ удаляемого элемента до $$-\fy$$, применяется всплытие, всплывший элемент удаляется как минимальный. Трудоемкость — $$O(\log n)$$.

Фибоначчиевы кучи

Название рассматриваемых куч связано с использованием чисел Фибоначчи при анализе трудоемкости выполнения операций. В отличие от биномиальных куч, в которых операции вставки, поиска элемента с минимальным ключом, удаления, уменьшения ключа и слияния выполняются за время $$O(\log n)$$, в фибоначчиевых кучах они выполняются более эффективно. Операции, не требующие удаления элементов, в этих кучах имеют учетную стоимость $$O(1)$$. Теоретически фибоначчиевы кучи особенно полезны, если число операций удаления мало по сравнению с остальными операциями. Такая ситуация возникает во многих приложениях.

Например, алгоритм, обрабатывающий граф, может вызывать процедуру уменьшения ключа для каждого ребра графа. Для плотных графов, имеющих много ребер, переход от $$O(\log n)$$ к $$O(1)$$ в оценке времени работы этой операции может привести к заметному уменьшению общего времени работы. Наиболее быстрые известные алгоритмы для задач построения минимального остовного дерева или поиска кратчайших путей из одной вершины используют фибоначчиевы кучи.

К сожалению, скрытые константы в асимптотических оценках трудоемкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные ( $$d$$ -ичные) кучи на практике эффективнее. С практической точки зрения желательно придумать структуру данных с теми же асимптотическими оценками, но с меньшими константами. Такие кучи будут рассмотрены в следующих разделах.

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

Строение фибоначчиевой кучи. Каждая фибоначчиева куча состоит из нескольких деревьев. В отличие от биномиальных деревьев, здесь дети любого узла могут записываться в любом порядке. Они связываются в двусторонний циклический список. Каждый узел $$x$$ этого списка имеет поля $${\rm left} [x]$$ и $${\rm right}[x]$$, указывающие на его соседей в списке. На рис. 7.2 показано схематическое строение фибоначчиевой кучи.

Двусторонние циклические списки удобны по двум причинам. Во-первых, из такого списка можно удалить любой узел за время $$O(1)$$. Во-вторых, два таких списка можно соединить в один за время $$O(1)$$.

Помимо указанной информации, каждый узел имеет поле $${\rm degree}[x]$$, где хранится его степень (число детей), а также поле $${\rm mark} [x]$$. В этом поле хранится булевское значение. Смысл его таков: $${\rm mark}[x]$$ истинно, если узел $$x$$ потерял ребенка после того, как он в последний раз сделался чьим-либо потомком. Позже будет ясно, как и когда это поле используется.

Корни деревьев, составляющих фибоначчиеву кучу, также связаны с помощью указателей $${\rm left}$$ и $${\rm right}$$ в двусторонний циклический список, называемый корневым списком. Таким образом, каждый узел фибоначчиевой кучи представляется записью вида$$\eq*{ {\rm Node} = [{\rm key}, {\rm left}, {\rm right}, {\rm parent}, {\rm child}, {\rm degree}, {\rm mark}]. }$$

Доступ к куче $$H$$ производится ссылкой $${\rm minH}$$ на узел с минимальным ключом. Кроме того, общее число узлов задается атрибутом $$n[H]$$.

Потенциал. При анализе учетной стоимости операций используют метод потенциала. Пусть $$t(H)$$ — число деревьев в корневом списке кучи $$H$$, а $$m(H)$$ — количество помеченных узлов. Потенциал определяется формулой$$\eq*{ \phi(H) = t(H) + 2 m (H). }$$

В каждый момент времени в памяти может храниться несколько куч; общий потенциал по определению равен сумме потенциалов всех этих куч. В дальнейшем мы выберем единицу измерения потенциала так, чтобы единичного изменения потенциала хватало для оплаты $$O(1)$$ операций (формально говоря, мы умножим потенциал на подходящую константу). В начальном состоянии нет ни одной кучи и потенциал равен $$0$$. Как и положено, потенциал всегда неотрицателен.

Максимальная степень Через $$D(n)$$ обозначим верхнюю границу для степеней узлов в кучах, которые могут появиться при выполнении операций. Аргументом функции $$D$$ является общее число всех узлов в куче, обозначаемое через $$n$$.

Мы не будем углубляться в анализ трудоемкости операций с фибоначчиевыми кучами, отсылая читателя к соответствующей литературе [7], [19] скажем только, что $$D(n) = O(\log n)$$ и все операции, кроме операции удаления элемента, имеют амортизационную трудоемкость $$O(1)$$, а операция удаления — $$O(\log n)$$.

Фибоначчиевы кучи ввел М.Фредман и Р.Тарьян [17]. В их статье описаны также приложения фибоначчиевых куч к задачам о кратчайших путях из одной вершины, о кратчайших путях для всех пар вершин, о паросочетаниях с весами и о минимальном покрывающем дереве.

Впоследствии Д.Дрисколл и Р.Тарьян [16] разработали структуру данных, называемую $${\rm relaxed heaps}$$, как замену для фибоначчиевых куч. Есть две разновидности такой структуры данных. Одна из них дает те же оценки учетной стоимости, что и фибоначчиевы кучи. Другая — позволяет выполнять операцию $${\rm DecreaseKey}$$ за время $$O(1)$$ в худшем случае, а операции $${\rm ExtractMin}$$ и Delete — за время $$O(\log n)$$ в худшем случае. Эта структура данных имеет также некоторые преимущества по сравнению с фибоначчиевыми кучами при использовании в параллельных алгоритмах.