Биномиальная куча

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

Определение:

Биномиальное дерево [math]B_k[/math] — дерево, определяемое для каждого [math]k = 0, 1, 2, \dots [/math] следующим образом: [math]B_0[/math] — дерево, состоящее из одного узла высоты [math]0[/math], то есть состоит из одного узла; [math]B_k[/math] состоит из двух биномиальных деревьев [math]B_{k-1}[/math], связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.

Пример биномиальных деревьев [math]B_0, B_2, B_3[/math]

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

Биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами:

• имеет [math]2^k[/math] узлов;

Так как в дереве порядка [math]k+1[/math] вдвое больше узлов, чем в дереве порядка [math]k[/math], а в дереве нулевого порядка [math]1 = 2^0[/math] узел, то дерево порядка [math]k[/math] имеет [math]2^k[/math] узлов.

• имеет высоту [math]k[/math];

Так как в дереве порядка [math]k+1[/math] высота больше на [math]1[/math] (так как мы подвешиваем к текущему дереву дерево того же порядка), чем в дереве порядка [math]k[/math], а в дереве нулевого порядка высота [math]0[/math] , то дерево порядка [math]k[/math] имеет высоту [math]k[/math].

• имеет ровно [math]{k\choose i}[/math] узлов на высоте [math]i = 0, 1, 2, \dots[/math];

Докажем по индукции:

База [math]k = 1[/math] — верно. Пусть для некоторого [math]k [/math] условие верно, то докажем, что для [math]k + 1[/math] это также верно:

Рассмотрим [math]i[/math] уровень дерева [math]B_{k+1}[/math]. Дерево [math]B_{k+1}[/math] было получено подвешиванием одного дерева порядка [math]k[/math] к другому. Тогда на [math]i[/math] уровне дерева [math]B_{k+1}[/math] всего узлов [math]{k\choose i} + {k\choose {i - 1}}[/math], так как от подвешенного дерева в дерево порядка [math]k+1[/math] нам пришли узлы глубины [math]i-1[/math]. То для [math]i[/math] уровня дерева [math]B_{k+1}[/math] количество узлов [math]{k\choose i} + {k\choose {i - 1}} ={{k + 1}\choose i} [/math]. То свойство доказано.

• имеет корень степени [math]k[/math]; степень всех остальных вершин меньше степени корня биномиального дерева;

Так как в дереве порядка [math]k+1[/math] степень корня больше на [math]1[/math], чем в дереве порядка [math]k[/math], а в дереве нулевого порядка степень корня [math]0[/math], то дерево порядка [math]k[/math] имеет корень степени [math]k[/math]. И так как при таком увеличении порядка(при переходе от дерева порядка [math]k[/math] к [math]k+1[/math]) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться.

• максимальная степень произвольного узла в биномиальном дереве с [math]n[/math] узлами равна [math]\log(n)[/math].

Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Так как степень корня дерева порядка [math]k[/math] равна [math]k[/math], а узлов в этом дереве [math]n = 2^k[/math], то прологарифмировав обе части получаем, что [math]k=O(\log(n))[/math], то степень произвольного узла не более [math]\log(n)[/math].

Биномиальная куча

Определение:

Биномиальная пирамида (куча) — представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам: Каждое биномиальное дерево в пирамиде подчиняется свойству неубывающей пирамиды: ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей пирамиды дерево). Для любого неотрицательного целого [math]k[/math] найдется не более одного биномиального дерева, чей корень имеет степень [math]k[/math].

Представление биномиальных куч

Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:

• [math]key[/math] — ключ (вес) элемента;
• [math]parent[/math] — указатель на родителя узла;
• [math]child[/math] — указатель на левого ребенка узла;
• [math]sibling[/math] — указатель на правого брата узла;
• [math]degree[/math] — степень узла (количество дочерних узлов данного узла).

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

Операции над биномиальными кучами

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

insert	[math]O(\log(n))[/math]
getMinimum	[math]O(\log(n))[/math]
extractMin	[math]\Theta(\log(n))[/math]
merge	[math]\Omega(\log(n))[/math]
decreaseKey	[math]\Theta(\log(n))[/math]
delete	[math]\Theta(\log(n))[/math]

Обозначим нашу кучу за [math]H[/math]. То пусть [math]H.head[/math] — указатель на корень биномиального дерева минимального порядка этой кучи. Изначально [math]H.head = null[/math], то есть пирамида не содержит элементов.

getMinimum

Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных [math]\infty[/math], нет).

Так как корней в этом списке не более [math]\lfloor \log(n) \rfloor + 1[/math], то операция выполняется за [math]O(\log(n))[/math].

При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем [math]1[/math].

merge

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

Для этого нам надо сначала слить списки корней [math]H_1, H_2[/math] в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. Для каждого элемента списка известна ссылка на следующего и предыдущего корня. Свойство пирамиды обеспечивает нам в новом списке наличие не более двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. Рассмотрим подробнее процесс прохождения по этому списку:

Если текущий корень имеет разные степени с следующим за ним, то ничего с ним не делаем и продолжаем цикл. Это дерево в итоге останется в таком виде в конечной куче(случай [math]a[/math] на рисунке). Если же степень текущего элемента равна степеням последующих двух вершин(это может случится в том случае, если в каждом из двух исходных деревьев был корень с этой степенью и еще одно дерево образовалось в ходе текущего слияния деревьев; причем более, чем трех корней с одинаковой степенью быть не может по нашему алгоритму и начальным условиям), то оставим это дерево нетронутым, но после на следующем шаге сольем два других дерева с этой степенью. Иными словами переходим к следующей вершине, в которой уже будет происходить слияние(случай [math]b[/math] на рисунке). В последнем случае мы имеем лишь две подряд вершины с одинаковой степенью корней. В этой ситуаций мы дерево с большим значением в корне вершины подвешиваем к дерево с меньшим значением в корне (случаи [math] c, d[/math] на рисунке).

Примечание. На рисунке [math]sibling[next-x][/math] — следующий элемент в списке для [math]next-x[/math]

Пример пирамиды до merge и после:

insert

Необходимо просто создать биномиальную пирамиду [math]H'[/math] с одним узлом за время [math]O(1)[/math] и объединяет ее с биномиальной пирамидой [math]Н[/math], содержащей [math]n[/math] узлов, за время [math]O(\log(n))[/math].

extractMin

Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел. Процедура выполняется за время [math]O(\log n)[/math], поскольку всего в списке [math]O(\log n)[/math] корней биномиальных деревьев. И всего у найденного дерева [math] k [/math] порядка(с минимальным значением ключа) ровно [math] k [/math] детей, то сложность перебора этих детей будет тоже [math]O(\log n)[/math]. То общая асимптотика [math]O(\log n) + O(\log n) = O(\log n)[/math].

 Node extractMin(H) {
   //поиск корня х с минимальным значением ключа в списке корней Н
   min = [math]\infty[/math];
   x = null;
   curx = H.head;
   while curx [math]\ne[/math] null {
     if curx.key < min {
       min = curx.key;
       x = curx;  
     }
     curx = curx.next;
   }
   //удаление найденного корня x из списка корней деревьев кучи
   x.prev.next = x.next;
   x.next.prev = x.prev;
   
   //добавление детей элемента x в кучу.
   H' = null;  
   curx = x.child;
   while curx [math]\ne[/math] null {
     p[curx] = null; // удаление элемента x из предков curx
     H'.head = curx;
     H = merge(H, H'); // слияние нашего дерева с текущим деревом H'  
     curx = curx.sibling;
   }
   return x;
 }

Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи. Все действия выполняются за время [math]O(\log n)[/math], так что общее время работы процедуры есть [math]O(\log n)[/math].

decreaseKey

Следующая процедура уменьшает ключ элемента [math]x[/math] биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время [math]O(\log n)[/math], поскольку глубина вершины [math]x[/math] есть [math]O(\log n)[/math] (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.

 void decreaseKey(H, x, k) { 
  if k > key[x] then
     return;
   key[x] = k;
   y = x;
   z = p[y];
   //поднимаем текущий элемент x с новым ключом k, пока
   //это значение меньше значения в родительской вершине 
   while z [math]\ne[/math] null and key[y] < key[z] do {
     swap(key[y], key[z]);
     y = z;
     z = p[y];
   }
 }

Пример работы процедуры проиллюстрирован на рисунке ([math]y[/math] — уменьшаемый элемент, [math]z[/math] — его предок).

delete

Удаление ключа сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения, а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время [math]O(\log n)[/math].

 void delete(H, x) {
   //уменшение ключа до минимально вохможного значения
   decreaseKey(H, x, [math]-\infty[/math]);
   //удаление "всплывшего" элемента
   extractMin(H);
 }

Источники

• Биномиальные кучи — INTUIT.ru
• Binomial heap — Wikipedia
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538-558. — ISBN 5-8489-0857-4