Изменения
Отмена правки 9928 участника 192.168.0.2 (обсуждение)
'''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> - дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.}}
Пример биномиального дерева для k = 0, 1, 2, 3.
[[Файл:Example.jpg|325px|]]
'''Свойства биномиальных деревьев. '''
Биномиальное дерево <tex>B_k</tex> с n вершинами:
*имеимеет <tex>2^k</tex> узлов;*имеет высоту k;*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;*имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева;*максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\log(n)</tex>. {{Определение|definition='''Биномиальная пирамида ([[Двоичная куча|куча]]) H''' {{---}} представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам '''биномиальных пирамид'''.*Каждое биномиальное дерево в Н подчиняется свойству '''неубывающей пирамиды''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойсвом неубывающей прирамиды дерево).*Для любого неотрицательного целого k найдется не более одного биномиального дерева Н, чей корень имеет степень K.}} ==== Представление биномиальных куч ====Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:*''key'' {{---}} ключ (вес) элемента;*''parent'' {{---}} указатель на родителя узла;*''child'' {{---}} указатель на левого ребенка узла;*''sibling'' {{---}} указатель на правого брата узла;*''degree'' {{---}} степень узла (количество дочерних узлов данного узла). Корни деревьев, их которых состоит пирамида, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в неубывающем порядке.Доступ к куче осуществляется ссылкой на первый корень в списке корней. == Операции над биномиальными пирамидами == ---- Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.{| border="1" |Make_Heap |<tex>\Theta(1)</tex> |- |Insert |<tex>O(\log(n))</tex> |- |Minimum |<tex>O(\log(n))</tex> |- |Extract_Min |<tex>\Theta(\log(n))</tex> |- |Union |<tex>\Omega(\log(n))</tex> |- |Decrease_Key |<tex>\Theta(\log(n))</tex> |- |Delete |<tex>\Theta(\log(n))</tex> |} === Make_Heap ===Для создания пустой биномиальной приамиды процедура Make_Binomial_Heap просто выделяет память и возвращает объект H, где head[H] = nil, то есть пирамида не содержит элементов. === Minimum ===Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет). Асимптотика этой операции получается из того, что корней в этом списке не более <tex>\lfloor \log(n) \rfloor + 1</tex>. При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем 1. [[Файл:Example2.jpg]] === Union ===Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций. Для этого нам надо сначала слить списки корней <tex>H_1, H_2</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. Свойство пирамиды обеспечивает нам в новом списке наличие не более двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. На каждом шаге нам надо расмотреть несколько случаев. * Рассматриваемое дерево и следующее за ним имеют разные степени (случай ''a'' на рисунке). Ситуация тривиальна и не требует никаких действий. Переходим к следующему шагу.* Текущее дерево и его два ближаших соседа справа (то есть те, которые встретятся на последующих итерациях) имеют одинаковые степени (случай ''b'' на рисунке). Эта ситуация хоть и не тривиальна, но ее следует оставить для следующего шага.* Если степень текущего и последующего деревьев одинакова (случай ''c-d'' на рисунке), то нам следует объединить их в новое дерево (сделав корнем вершину того дерева, чей ключ наименьший), степень которого будет на единицу больше той, что была ранее. [[Файл:Example3.jpg]] Пример пирамиды до Union и после: [[Файл:Example5.jpg]] === Inset ===Необходимо просто создать биномиальную пирамиду <tex>H'</tex> с одним узлом за время <tex>O(1)</tex> и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время <tex>O(\log(n))</tex>. === Extract_Min ===Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел: <code> Binomial_Heap_Extract_Min(H) поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н H' = Make_Binomial_Heap() Обращение порядка связанного списка дочерних узлов х, установка поля р каждого дочернего узла Н равным NIL присвоение указателю head[H'] адреса заголовка получающегося списка H = Binomial_Heap_Union(H, H') return x</code> Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи. Все действия выполняются за время <tex>O\log(n)</tex>, так что общее время работы процедуры есть <tex>O\log(n)</tex>. === Decrease_Key ===Следующая процедура уменьшает ключ элемента х биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время <tex>O\log(n)</tex>, поскольку глубина вершины х есть <tex>O\log(n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх. <code> Binomial_Heap_Decrease_Key(H, x, k) if k > key[x] then return key[x] = k y = x z = p[y] while (z <tex>\ne</tex> NIL and key[y] < key[z]) do swap(key[y], key[z]) y = z z = p[y]</code> Пример работы процедуры проиллюстрирован на рисунке (y - уменьшаемый элемент, z - его предок). [[Файл:Example6.jpg|600px]] === Delete ===Удаление ключа сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения, а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>O\log(n)</tex>. <code> Binomial_Heap_Delete(H, x) Binomial_Heap_Decrease_Key(H, x, -<tex>\infty</tex>) Binomial_Heap_Extract_Min(H)</code> == Источники ==----* [http://www.intuit.ru/department/algorithms/dscm/7/ INTUIT.ru |Биномиальные кучи]* [http://en.wikipedia.org/wiki/Binomial_heap Wikipedia | Binomial_heap]* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 538-558.
