Изменения
Исправлены две пунктуационные ошибки.
[[Файл: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> {{---}} дерево, состоящее из одного узла высоты <tex>0</tex>, то есть состоит из одного узла; <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>i</tex> уровень дерева <tex>B_{k+1}</tex>. Дерево <tex>B_{k+1}</tex> было получено подвешиванием одного дерева порядка <tex>k</tex> к другому. Тогда на <tex>i</tex> уровне дерева <tex>B_{k+1}</tex> всего узлов <texdpi = "165">{k\choose i} </tex> <tex>+ </tex> <tex dpi = "165">{k\choose {i - 1}}</tex>, так как от подвешенного дерева в дерево порядка <tex>k+1</tex> нам пришли узлы глубины <tex>i-1</tex>. То для <tex>i</tex> -го уровня дерева <tex>B_{k+1}</tex> количество узлов <texdpi = "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\choose i}</tex> узлов на высоте <tex>i</tex>.}}
= Биномиальная куча=
{{Определение
|definition=
'''Биномиальная пирамида куча''' ([[Двоичная куча|куча]]) англ. ''binomial heap'' {{---}} ) представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:*Каждое каждое биномиальное дерево в пирамиде куче подчиняется свойству '''[[Двоичная куча|неубывающей пирамидыкучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей пирамиды кучи дерево).,*Для для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <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"1bgcolor=#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[H]</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head[H] = null</tex>, то есть пирамида куча не содержит элементов.
=== getMinimum ===
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).
=== merge ===
Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за <tex>\Omega(\log n)</tex>.
=== insert ===
=== extractMin ===
Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел. Рассмотрим пошагово алгоритм:* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <tex>B_k</tex>. Время работы этого шага алгоритма <tex>\Theta(\log n)</tex>.* Удаляем дерево <tex>B_k</tex> из кучи <tex>H</tex>. Иными словами, удаляем его корень из списка корней кучи. Это можно сделать за время <tex>O(1)</tex>.* Пусть <tex>H'</tex> {{---}} куча детей найденного корня. При этом мы для каждого из ребенка устанавливаем указатель на предка равным <tex>null</tex>. После этого сливаем кучу <tex>H'</tex> c <tex>H</tex> за <tex>\Omega(\log n)</tex>. Процедура выполняется за время <tex>O\Theta(\log n)</tex>, поскольку всего в списке <tex>O\Theta(\log n)</tex> корней биномиальных деревьев. И всего у найденного дерева <tex> k </tex> порядка(с минимальным значением ключа) ровно <tex> k </tex> детей, то сложность перебора этих детей будет тоже <tex>O\Theta(\log n)</tex>. То общая асимптотика А процесс слияния выполняется за <tex>O\Omega(\log n) + O(</tex>. Таким образом, операция выполняется <tex>\log n) = OTheta(\log n)</tex>. [[Файл:BinHeapExampleNew31.png|700px|Примеp извлечения минимума]]
<code>
</code>
=== decreaseKey ===
Следующая процедура уменьшает ключ элемента <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверхкак в обычной куче. Процедура выполняется за время <tex>O\Theta(\log n)</tex>, поскольку глубина вершины <tex>x</tex> в худшем случае есть <tex>O\Theta(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
<code>
</code>
Пример работы процедуры проиллюстрирован на рисунке (<tex>y</tex> {{---}} уменьшаемый элемент, <tex>z</tex> {{---}} его предок).
[[Файл:binHeapExample3binHeapExample3_2.png|400px370px]]
=== delete ===
Удаление ключа сводится к двум предыдущим операциям<math>\mathrm {decreaseKey}</math> и <math>\mathrm {extractMin}</math>: мы уменьшаем сначала нужно уменьшить ключ до минимально возможного значения, а затем удаляем извлечь вершину с минимальным ключом. В процессе выполнения процедуры это значение этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>O\Theta(\log n)</tex>, поскольку каждая из операций, которые используется в реализации, работают за <tex>\Theta(\log n)</tex>.
<code>
</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://enwww.wikipedialektorium.orgtv/wikilecture/Binomial_heap Binomial heap — Wikipedia?id=14234 Лекция А.С. Станкевича по приоритетным очередям]* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538-558538—558. — ISBN 5-8489-0857-4 [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных]]