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

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

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

Пример биномиального дерева для k = 0, 1, 2.

Свойства биномиальных деревьев. Биномиальное дерево [math]B_k[/math] с n вершинами:

• имеет [math]2^k[/math] узлов;
• имеет высоту k;
• имеет ровно [math]{k\choose i}[/math] узлов на высоте [math]i = 0, 1, 2, \dots[/math];
• имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева;
• максимальная степень произвольного узла в биномиальном дереве с n узлами равна [math]\log(n)[/math].

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

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

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

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

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

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

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

---

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

Make_Heap	[math]\Theta(1)[/math]
Insert	[math]O(\log(n))[/math]
Minimum	[math]O(\log(n))[/math]
Extract_Min	[math]\Theta(\lоg(n))[/math]
Union	[math]\Omega(\lоg(n))[/math]
Decrease_Key	[math]\Theta(\lоg(n))[/math]
Delete	[math]\Theta(\lоg(n))[/math]

Make_Heap

Для создания пустой биномиальной приамиды процедура Make_Binomial_Heap просто выделяет память и возвращает объект H, где head[H] = nil, то есть пирамида не содержит элементов.

Minimum

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

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

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

Union

Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций. Процедура Binomial_Heap_Union многократно связывает биномиальные деревья с корнями одинаковой степени. Приведенная далее процедура связывает дерево [math]B_k[/math] с корнем y с деревом [math]B_{k-1}[/math] с корнем z, делая z родительским узлом для y, после чего узел z становится корнем дерева [math]B_k[/math].

 Binomial_Link(y, z)
   p[y] = z
   sibling[y] = child[z]
   child[z] = y
   degree[z]++

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

 Binomial_Heap_Union([math]H_1, H_2[/math])
 H = Make_Binomial_Heap()
 head[H] = Binomial_Heap_Merge([math]H_1, H_2[/math])
 delete [math]H_1, H_2[/math] //удаление объектов, но не списков, на которые они указывают
 if head[H] = NIL
   then return H
 prex_x = NIL
 x = head[H]
 next_x = sibling[x]
 while next_x [math]\ne[/math] NIL do
   if (degree[x] [math]\ne[/math] degree[next_x]) or (sibling[next_x] [math]\ne[/math] NIL and degree[sibling[next_x]] = degree[x]) then
     prex_x = x
   else
     if key[x] <= key[next_x] then
       sibling[x] = sibling[next_x]
       Binomial_Link(next_x, x)
     else
       if prev_x = NIL then
         head[H] = next_x
       else
         sibling[prev_x] = next_x
       Binomial_Link(x, next_x)
       x = next_x
   next_x = sibling[x]

Inset

Приведенная ниже процедура вставляет узел х в биномиальную пирамиду Н (предполагается, что для х уже выделена память и поле key[x] уже заполнено):

 Binomial_Heap_Insert(H, x)
   H' = Make_Binpmial_Heap
   p[x] = NIL
   child[x] = NIL
   sibling[x] = NIL
   degree[x] = 0
   head[H'] = x
   H = Binomial_Heap_Union(H, H')

Процедура просто создает биномиальную пирамиду H' с одним узлом за время О(1) и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время О(lg(n)).

Extract_Min

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

 Binomial_Heap_Extract_Min(H)
   поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н
 H' = Make_Binomial_Heap()
 Обращение порядка связанного списка дочерних узлов х,
   установка поля р каждого дочернего узла Н равным NIL
   присвоение указателю head[H'] адреса заголовка 
   получающегося списка
 H = Binomial_Heap_Union(H, H')
 return x

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

Decrease_Key

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

 Binomial_Heap_Decrease_Key(H, x, k)
   if k > key[x] then
     return
   key[x] = k
   y = x
   z = p[y]
   while (z [math]\ne[/math] NIL and key[y] < key[z]) do
     swap(key[y], key[z])
   y = z
   z = p[y]

Delete

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

 Binomial_Heap_Delete(H, x)
   Binomial_Heap_Decrease_Key(H, x, -[math]\infty[/math])
   Binomial_Heap_Extract_Min(H)

Источники

---

• INTUIT.ru |Биномиальные кучи
• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 538-558.