Изменения

Перейти к: навигация, поиск

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

3716 байт добавлено, 14:31, 17 октября 2015
Исправлены две пунктуационные ошибки.
{{Определение
|definition =
'''Биномиальное дерево <tex>B_k</tex>''' (англ. ''binomial tree'') {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{---}} дерево, состоящее из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны связанных вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.
}}
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет <tex>2^k</tex> узлов.
|proof=
Докажем по индукции:
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет высоту <tex>k</tex>;.
|proof=
Докажем по индукции:
{{Определение
|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="1center" bgcolor=#EEEEFF! Операция || Время работы |-align="center"bgcolor=#FFFFFF |<mathtex>\mathrm {insert}</mathtex> ||<tex>O(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<mathtex>\mathrm {getMinimum}</mathtex> ||<tex>O(\log n)</tex> |-align="center" bgcolor=#FFFFFF ||<mathtex>\mathrm {extractMin}</mathtex> ||<tex>\Theta(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<mathtex>\mathrm {merge}</mathtex> ||<tex>\Omega(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<mathtex>\mathrm {decreaseKey}</mathtex> ||<tex>\Theta(\log n)</tex> |-align="center" bgcolor=#FFFFFF |<mathtex>\mathrm {delete}</mathtex> ||<tex>\Theta(\log n)</tex> |}
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов.
=== getMinimum ===
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>inf\infty</tex>, нет).
Так как корней в этом списке не более <tex>\lfloor \log n \rfloor + 1</tex>, то операция выполняется за <tex>O(\log n)</tex>.
[[Файл:binHeapExample1_1.png|370px]]
 
При использовании указателя на биномиальное дерево, которое содержит минимальный элемент, время для этой операции может быть сведено к <tex>O(1)</tex>. Указатель должен обновляться при выполнении любой операции, кроме <tex>\mathrm{getMinimum}</tex>. Это может быть сделано за <tex>O(\log n)</tex>, не ухудшая время работы других операций.
=== merge ===
<code>
'''BinomialHeap''' merge(H1 : '''BinomialHeap''', H2 : '''BinomialHeap'''):
'''if''' H1 == ''null''
'''return''' H2
Рассмотрим пошагово алгоритм:
* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <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>\Theta(\log n)</tex>, поскольку всего в списке <tex>\Theta(\log n)</tex> корней биномиальных деревьев. И всего у найденного дерева <tex> k </tex> порядка (с минимальным значением ключа) ровно <tex> k </tex> детей, то сложность перебора этих детей будет тоже <tex>\Theta(\log n)</tex>. А процесс слияния выполняется за <tex>\Omega(\log n)</tex>. Таким образом , операция выполняется <tex>\Theta(\log n)</tex>.
[[Файл:BinHeapExampleNew31.png|700px|Примеp извлечения минимума]]
<code>
'''Node''' extractMin(H : '''BinomialHeap''') : <font color = "green">//поиск корня х с минимальным значением ключа в списке корней Н: </font> min = ''inf''<tex>\infty</tex>
x = ''null''
xBefore = ''null''
<code>
'''function''' decreaseKey(H : '''BinomialHeap''', x : '''Node''', k : '''int''') :
'''if''' k > key[x] <font color = "green">// проверка на то, что текущий ключ x не меньше передаваемого ключа k </font>
'''return'''
<code>
'''function''' delete(H : '''BinomialHeap''', x : '''Node''') : decreaseKey(H, x, <tex>-''inf''\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://enwww.wikipedialektorium.orgtv/wikilecture/Binomial_heap Binomial heap — Wikipedia?id=14234 Лекция А.С. Станкевича по приоритетным очередям]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538—558. — ISBN 5-8489-0857-4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных‏‎]]
Анонимный участник

Навигация