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

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

Биномиальное дерево [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], связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.

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

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

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

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

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

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

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

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

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

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

Make_Heap	[math]\Theta(1)[/math]
Insert	[math]O(\lg(n))[/math]
Minimum	[math]O(\lg(n))[/math]
Extract_Min	[math]\Theta(\lg(n))[/math]
Union	[math]\Omega(\lg(n))[/math]
Decrease_Key	[math]\Theta(\lg(n))[/math]
Delete	[math]\Theta(\lg(n))[/math]

Make_Heap

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

Minimum

Процедура Binomial_Heap_Minimum возвращает указатель на узел с минимальным ключом. Приведенный ниже певдокод предполагает, что ключей, равных [math]\infty[/math], нет.

Binomial_Yeap_Minimum(H) y = NIL x = head[H] min = [math]\infty[/math] while x [math]\ne[/math] NIL do

 if key[x] < min then
   y = x
 x = sibling[x]

return y

lis = 0           // длина НВП
a = (n, 0)        // заполняем нулями
pred = (n, -1)    // -1 - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности
a[1] = 1         
For i = 2 to n
  For j = 1 to i - 1
    If (x[i] > x[j]) and (a[j] + 1 > a[i]) // нашли более оптимальную подпоследовательность
      a[i] = a[j]+1
      pred[i] = j
    lis = max(lis, a[i])