Изменения
Исправлены две пунктуационные ошибки.
[[Файл:binHeapExample.png|thumb|325px|Пример биномиальных деревьев <tex>B_0, B_2, B_3</tex>]]
= Биномиальное дерево =
{{Определение
|definition='''Биномиальное дерево <tex>B_k</tex>''' (англ. ''binomial tree'') {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{--- }} дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны связанных вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.}}''' == Свойства биномиальных деревьев. '''== {{Утверждение|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n </tex> вершинамиимеет <tex>2^k</tex> узлов.|proof=Докажем по индукции:*База <tex>k = 1</tex> {{---}} верно. Пусть для некоторого <tex>k </tex> условие верно, то докажем, что для <tex>k + 1</tex> это также верно: Так как в дереве порядка <tex>k+1</tex> вдвое больше узлов, чем в дереве порядка <tex>k</tex>, то дерево порядка <tex>k+1</tex> имеет <tex>2^k\cdot 2 = 2^{k+1}</tex> узлов;. Переход доказан, то биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет <tex>2^k</tex> узлов.}} {{Утверждение|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет высоту <tex>k</tex>.|proof=Докажем по индукции: База <tex>k = 1</tex> {{---}} верно. Пусть для некоторого <tex>k </tex> условие верно, то докажем, что для <tex>k + 1</tex> это также верно: *Так как в дереве порядка <tex>k+1</tex> высота больше на <tex>1</tex> (так как мы подвешиваем к текущему дереву дерево того же порядка), чем в дереве порядка <tex>k</tex>, то дерево порядка <tex>k+1</tex> имеет высоту <tex>k + 1</tex>. Переход доказан, то биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет высоту <tex>k;</tex>. }} {{Утверждение*|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет ровно <texdpi = "165">{k\choose i}</tex> узлов на высоте <tex>i </tex>.|proof=Докажем по индукции: База <tex>k = 01</tex> {{---}} верно. Пусть для некоторого <tex>k </tex> условие верно, то докажем, что для <tex>k + 1</tex> это также верно: Рассмотрим <tex>i</tex> уровень дерева <tex>B_{k+1}</tex>. Дерево <tex>B_{k+1}</tex> было получено подвешиванием одного дерева порядка <tex>k</tex> к другому. Тогда на <tex>i</tex> уровне дерева <tex>B_{k+1}</tex> всего узлов <tex dpi = "165"> {k\choose i} </tex> <tex>+</tex> <tex dpi = "165">{k\choose {i - 1}}</tex>, 2так как от подвешенного дерева в дерево порядка <tex>k+1</tex> нам пришли узлы глубины <tex>i-1</tex>. То для <tex>i</tex>-го уровня дерева <tex>B_{k+1}</tex> количество узлов <tex dpi = "165"> {k\choose i}</tex> <tex>+</tex> <tex dpi = "165">{k\choose {i - 1}}</tex> <tex>=</tex> <tex dpi = "160">{{k + 1}\choose i} </tex>. Переход доказан, то биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет ровно <tex dpi = "165"> {k\dotschoose i}</tex> узлов на высоте <tex>i</tex>;.}} {{Утверждение*|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет корень степени <tex>k</tex>; степерь степень всех остальных вершин меньше степени корня биномиального дерева. Кроме того, если дочерние узлы ;|proof=Так как в дереве порядка <tex>k+1</tex> степень корня пронумеровать слева направо числами больше на <tex> k - 1</tex>, чем в дереве порядка <tex>k - 2, \dots</tex>, а в дереве нулевого порядка степень корня <tex>0</tex>, то i-й дочерний узел корня является корнем биномиального дерево порядка <tex>k</tex> имеет корень степени <tex>k</tex>. И так как при таком увеличении порядка (при переходе от дерева порядка <tex>k</tex> к <tex>B_ik+1</tex>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться. }} {{Утверждение*|statement=В биномиальном дереве <tex>B_k</tex> с <tex>n</tex> вершинами максимальная степень произвольного узла равна <tex>\log n</tex>.|proof=Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Так как степень корня дерева порядка <tex>k</tex> равна <tex>k</tex>, а узлов в биномиальном этом дереве с <tex>n узлами равна = 2^k</tex>, то прологарифмировав обе части получаем, что <tex>k=O(\lg (log n)</tex>, то степень произвольного узла не более <tex>\log n</tex>.}} = Биномиальная куча=
{{Определение
|definition=
'''Биномиальная пирамида Hкуча''' (англ. ''binomial heap'' {{---}} ) представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам '''биномиальных пирамид'''.:*Каждое каждое биномиальное дерево в Н куче подчиняется свойству '''[[Двоичная куча|неубывающей пирамидыкучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойсвом свойством неубывающей прирамиды кучи дерево).,* Для для любого неотрицательного целого <tex>k </tex> найдется не более одного биномиального дерева Н, чей корень имеет степень K<tex>k</tex>.}} == Представление биномиальных куч ==Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей:*<tex>key</tex> {{---}} ключ (вес) элемента,*<tex>parent</tex> {{---}} указатель на родителя узла,*<tex>child</tex> {{---}} указатель на левого ребенка узла,*<tex>sibling</tex> {{---}} указатель на правого брата узла,*<tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла). Корни деревьев, из которых состоит куча, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в возрастающем порядке.Доступ к куче осуществляется ссылкой на первый корень в списке корней. == Операции над биномиальными кучами== Рассмотрим операции, которые можно производить с биномиальной кучей. Время работы указано в таблице:{| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF! Операция || Время работы |-align="center" bgcolor=#FFFFFF|<tex>\mathrm{insert}</tex>||<tex>O(\log n)</tex>|-align="center" bgcolor=#FFFFFF|<tex>\mathrm{getMinimum}</tex>||<tex>O(\log n)</tex>|-align="center" bgcolor=#FFFFFF||<tex>\mathrm{extractMin}</tex>||<tex>\Theta(\log n)</tex>|-align="center" bgcolor=#FFFFFF|<tex>\mathrm{merge}</tex>||<tex>\Omega(\log n)</tex>|-align="center" bgcolor=#FFFFFF|<tex>\mathrm{decreaseKey}</tex>||<tex>\Theta(\log n)</tex>|-align="center" bgcolor=#FFFFFF|<tex>\mathrm{delete}</tex>||<tex>\Theta(\log n)</tex>|}Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов. === getMinimum ===Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет). Так как корней в этом списке не более <tex>\lfloor \log n \rfloor + 1</tex>, то операция выполняется за <tex>O(\log n)</tex>. При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключом <tex>1</tex>. [[Файл:binHeapExample1_1.png|370px]] При использовании указателя на биномиальное дерево, которое содержит минимальный элемент, время для этой операции может быть сведено к <tex>O(1)</tex>. Указатель должен обновляться при выполнении любой операции, кроме <tex>\mathrm{getMinimum}</tex>. Это может быть сделано за <tex>O(\log n)</tex>, не ухудшая время работы других операций. === merge ===Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций. Вот в чем состоит ее суть: пусть есть две биномиальные кучи с <tex>H</tex> и <tex>H'</tex>.Размеры деревьев в кучах соответствуют двоичным числам <tex>m</tex> и <tex>n</tex>, то есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев <tex>B_{k-1}</tex> в дерево <tex>B_{k}</tex>. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, и считать его верхним (пример работы для одного случая приведен на рисунке справа; в другом случае подвешиваем наоборот).
<code>
[[Файл:BinHeapExampleNew31.png|700px|Примеp извлечения минимума]]
<code>
'''Node''' extractMin(H : '''BinomialHeap'''): <font color = "green">//поиск корня х с минимальным значением ключа в списке корней Н: </font>
min = <tex>\infty</tex>
x = ''null''
xBefore = ''null''
curx = H.head
curxBefore = ''null''
'''while''' curx != ''null''
'''if''' curx.key < min <font color = "green"> // релаксируем текущий минимум </font>
min = curx.key
x = curx
xBefore = curxBefore
curxBefore = curx
curx = curx.sibling
'''if''' xBefore == ''null'' <font color = "green"> //удаление найденного корня x из списка корней деревьев кучи</font>
H.head = x.sibling
'''else'''
xBefore.sibling = x.sibling
H' = ''null'' <font color = "green">//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на ''null'':</font>
curx = x.child
H'.head = x.child
'''while''' curx != ''null''
p[curx] = ''null'' <font color = "green">// меняем указатель на родителя узла curx </font>
curx = curx.sibling <font color = "green">// переход к следующему ребенку </font>
H = merge(H, H') <font color = "green">// слияние нашего дерева с деревом H' </font>
'''return''' x
</code>
=== decreaseKey ===
Следующая процедура уменьшает ключ элемента <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» как в обычной куче. Процедура выполняется за время <tex>\Theta(\log n)</tex>, поскольку глубина вершины <tex>x</tex> в худшем случае есть <tex>\Theta(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
<code>
'''function''' decreaseKey(H : '''BinomialHeap''', x : '''Node''', k : '''int'''):
'''if''' k > key[x] <font color = "green">// проверка на то, что текущий ключ x не меньше передаваемого ключа k </font>
'''return'''
key[x] = k
y = x
z = p[y]
'''while''' z != ''null'' '''and''' key[y] < key[z] <font color = "green">// поднимаем x с новым ключом k, пока это значение меньше значения в родительской вершине </font>
swap(key[y], key[z])
y = z
z = p[y]
</code>
Пример работы процедуры проиллюстрирован на рисунке (<tex>y</tex> {{---}} уменьшаемый элемент, <tex>z</tex> {{---}} его предок).
[[Файл:binHeapExample3_2.png|370px]]
=== delete ===
Удаление ключа сводится к операциям <math>\mathrm {decreaseKey}</math> и <math>\mathrm {extractMin}</math>: сначала нужно уменьшить ключ до минимально возможного значения, а затем извлечь вершину с минимальным ключом. В процессе выполнения процедуры этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>\Theta(\log n)</tex>, поскольку каждая из операций, которые используется в реализации, работают за <tex>\Theta(\log n)</tex>.
<code>
'''function''' delete(H : '''BinomialHeap''', x : '''Node'''):
decreaseKey(H, x, <tex>-\infty</tex>) <font color = "green">// уменьшение ключа до минимально возможного значения </font>
extractMin(H) <font color = "green">// удаление "всплывшего" элемента </font>
</code>
=== Персистентность ===
Биноминальную кучу можно сделать [[Персистентные структуры данных|персистентной]] при реализации на односвязных списках<ref>[https://github.com/kgeorgiy/okasaki/tree/master/Okasaki/Chapter3 Github {{---}} реализация на Haskell]</ref>. Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя. Односвязанные списки хороши с точки зрения функционального программирования, так как голова списка не будет достижима из потомков. Тогда при добавлениии новой версии в голову или удалении объявляя другую вершину новой головой мы не будем терять старые версии, которые останутся на месте, так как фактически односвязный список с операциями на голове это [[Персистентный стек|персистентный стек]], который является полностью персистентной функциональной структурой. При этом каждая версия будет поддерживать возможность изменения, что является полным уровнем персистентности. Также поддерживается операция <tex>\mathrm {merge}</tex> для всех версий биномиальных куч, что позволяет получать новую версию путём сливания старых. Это добавляет конфлюэнтный уровень персистентности.
== См. также ==
* [[Двоичная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]
* [[Куча Бродала-Окасаки]]
==Примечания==
<references />
== Источники информации ==
* [http://ru.wikipedia.org/wiki/Биномиальная_куча Википедия {{---}} Биномиальная куча]
* [http://en.wikipedia.org/wiki/Binomial_heap Wikipedia {{---}} Binomial heap]
* [http://www.intuit.ru/department/algorithms/dscm/7/ INTUIT.ru {{---}} Биномиальные кучи]
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538—558. — ISBN 5-8489-0857-4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]