Изменения

|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> вершинами имеет ровно <tex dpi = "165"> k\choose i</tex> узлов на высоте <tex>i</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> всего узлов <tex dpi = "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> количество узлов <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\choose i}</tex> узлов на высоте <tex>i</tex>.}}

Пример {{Утверждение|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет корень степени <tex>k</tex>; степень всех остальных вершин меньше степени корня биномиального дерева для ;|proof=Так как в дереве порядка <tex>k+1</tex> степень корня больше на <tex>1</tex>, чем в дереве порядка <tex>k = </tex>, а в дереве нулевого порядка степень корня <tex>0</tex>, то дерево порядка <tex>k</tex> имеет корень степени <tex>k</tex>. И так как при таком увеличении порядка (при переходе от дерева порядка <tex>k</tex> к <tex>k+1</tex>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, 2не будет нарушаться.

'''Свойства биномиальных деревьев. '''{{УтверждениеБиномиальное дерево |statement=В биномиальном дереве <tex>B_k</tex> с <tex>n </tex> вершинами:максимальная степень произвольного узла равна <tex>\log n</tex>.|proof=*имеет Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Так как степень корня дерева порядка <tex>2^k</tex> узлов;*имеет высоту k;*имеет ровно равна <tex>{k\choose i}</tex> , а узлов на высоте в этом дереве <tex>i n = 02^k</tex>, 1, 2то прологарифмировав обе части получаем, что <tex>k=O(\dotslog n)</tex>;*имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева;*максимальная , то степень произвольного узла в биномиальном дереве с n узлами равна не более <tex>\log(n)</tex>.}}

'''Биномиальная пирамида куча''' ([[Двоичная куча|куча]]) 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>, то есть куча не содержит элементов.

Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.{| border="1"== getMinimum === |Make_Heap |<tex>\ThetaДля нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (1)</tex> |- |Insert |предполагается, что ключей, равных <tex>O(\log(n))infty</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Так как корней в этом списке не более <tex>\lfloor \log n \rfloor + 1</tex>, то есть пирамида не содержит элементовоперация выполняется за <tex>O(\log n)</tex>.

=== Minimum ===Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагаетсяПри вызове этой процедуры для кучи, что ключейизображенной на картинке ниже, равных будет возвращен указатель на вершину с ключом <tex>\infty1</tex>, нет).

Асимптотика этой операции получается из того, что корней в этом списке не более <tex>\lfloor \log(n) \rfloor + 1</tex>[[Файл:binHeapExample1_1.png|370px]]

При вызове использовании указателя на биномиальное дерево, которое содержит минимальный элемент, время для этой процедуры для кучиоперации может быть сведено к <tex>O(1)</tex>. Указатель должен обновляться при выполнении любой операции, изображенной на картинке нижекроме <tex>\mathrm{getMinimum}</tex>. Это может быть сделано за <tex>O(\log n)</tex>, будет возвращен указатель на вершину с ключем 1не ухудшая время работы других операций.

[[Файл:Example2=== merge ===Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.jpg]]

=== Union ===Эта операция, соединяющая Вот в чем состоит ее суть: пусть есть две биномиальные кучи с <tex>H</tex> и <tex>H'</tex>. Размеры деревьев в кучах соответствуют двоичным числам <tex>m</tex> и <tex>n</tex>, то есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев <tex>B_{k-1}</tex> в дерево <tex>B_{k}</tex>. Надо только посмотреть, в однукаком из сливаемых деревьев корень меньше, используется и считать его верхним (пример работы для одного случая приведен на рисунке справа; в качестве подпрограммы большинством остальных операцийдругом случае подвешиваем наоборот).

Для этого нам надо сначала слить списки корней <tex>H_1, H_2</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке[[Файл:helpBinaryHeapBoris. Свойство пирамиды обеспечивает нам в новом списке наличие не более png|Пример слияние двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. На каждом шаге нам надо расмотреть несколько случаев.одного порядка]]

* Рассматриваемое дерево и следующее за ним имеют разные степени (случай ''a'' на рисунке). Ситуация тривиальна и не требует никаких действий. Переходим к следующему шагу.* Текущее дерево и его два ближаших соседа справа (то есть теРабота этой процедуры начинается с соединения корневых списков куч в единый список, которые встретятся на последующих итерациях) имеют одинаковые степени (случай ''b'' на рисунке). Эта ситуация хоть и не тривиальна, но ее следует оставить для следующего шага.* Если степень текущего и последующего деревьев одинакова (случай ''c-d'' на рисунке), то нам следует объединить в котором корневые вершины идут в порядке неубывания их в новое дерево (сделав корнем вершину того дерева, чей ключ наименьший), степень которого будет на единицу больше той, что была ранеестепеней.

[[Файл:Example3В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за <tex>\Omega(\log n)</tex>.jpg]]

Binomial_Heap_Extract_Min '''BinomialHeap''' merge(HH1 : '''BinomialHeap''', H2 : '''BinomialHeap'''): поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н'''if''' H1 == ''null'' '''return''' H2 '''if''' H2 == ''null'' '''return''' H1 H.head = ''null' ' <font color = Make_Binomial_Heap()"green"> // H {{---}} результат слияния </font> Обращение порядка связанного списка дочерних узлов х, curH = H.head <font color = "green"> // слияние корневых списков </font> установка поля р каждого дочернего узла Н равным NILcurH1 = H1.head присвоение указателю curH2 = H2.head[ '''while''' curH1 != ''null'' '''and''' curH2 != ''null'' '''if''' curH1.degree < curH2.degree curH.sibling = curH1 curH = curH1 curH1 = curH1.sibling '''else''' curH.sibling = curH2 curH = curH2 curH2 = curH2.sibling '''if''' curH1 == ''null'' '''while''' curH2 != ''null'' curH.sibling = curH2 curH2 = curH2.sibling '''else''' '''while''' curH1 != ''null'' curH.sibling = curH1 curH1 = curH1.sibling curH = H.head <font color = "green"> // объединение деревьев одной степени </font> '''while''' curH.sibling != ''null'' '''if''' curH.degree == curH.sibling.degree p[curH] адреса заголовка = curH.sibling tmp = curH.sibling получающегося списка curH.sibling = curH.sibling.child H curH = Binomial_Heap_Union(H, Htmp '''continue''') curH = curH.sibling '''return x''' H

Поскольку минимальный === insert ===Чтобы добавить новый элемент находится в корневом спискебиномиальную кучу нужно создать биномиальную кучу <tex>H'</tex> с единственным узлом, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размерасодержащим этот элемент, который надо за время <tex>O(1)</tex> и объединить ее с оставшейся частью биномиальной кучей <tex>H</tex> за <tex>O(\log n)</tex>, так как в данном случае куча <tex>H'</tex> содержит лишь одно дерево. === extractMin === Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучии возвращает указатель на извлеченный узел. Все действия выполняются Рассмотрим пошагово алгоритм:* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <tex>B_k</tex>. Время работы этого шага алгоритма <tex>\Theta(\log n)</tex>.* Удаляем дерево <tex>B_k</tex> из кучи <tex>H</tex>. Иными словами, удаляем его корень из списка корней кучи. Это можно сделать за время <tex>O(lgn1)</tex>.* Пусть <tex>H'</tex> {{---}} куча детей найденного корня. При этом мы для каждого из ребенка устанавливаем указатель на предка равным <tex>null</tex>. После этого сливаем кучу <tex>H'</tex> c <tex>H</tex> за <tex>\Omega(\log n)</tex>. Процедура выполняется за время <tex>\Theta(\log n)</tex>, так что общее время работы процедуры есть Oпоскольку всего в списке <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 = <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(lgnH, H') <font color = "green">// слияние нашего дерева с деревом H' </font> '''return''' x</code>

=== Decrease_Key decreaseKey ===Следующая процедура уменьшает ключ элемента х <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверхкак в обычной куче. Процедура выполняется за время O<tex>\Theta(lgn\log n)</tex>, поскольку глубина вершины х <tex>x</tex> в худшем случае есть O<tex>\Theta(lgn\log n) </tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.

Binomial_Heap_Decrease_Key '''function''' decreaseKey(H: '''BinomialHeap''', x: '''Node''', k: '''int'''): '''if ''' k > key[x] then <font color = "green">// проверка на то, что текущий ключ x не меньше передаваемого ключа k </font> '''return''' key[x] = k y = x z = p[y] '''while (''' z <tex>\ne</tex> NIL != ''null'' '''and ''' key[y] < key[z]) do<font color = "green">// поднимаем x с новым ключом k, пока это значение меньше значения в родительской вершине </font> swap(key[y], key[z]) y = z z = p[y]

Пример работы процедуры проиллюстрирован на рисунке (<tex>y</tex> {{---}} уменьшаемый элемент, <tex>z</tex> {{---}} его предок). [[Файл:binHeapExample3_2.png|370px]] === Delete delete ===Удаление ключа сводится к двум предыдущим операциям<math>\mathrm {decreaseKey}</math> и <math>\mathrm {extractMin}</math>: мы уменьшаем сначала нужно уменьшить ключ до минимально возможного значения, а затем удаляем извлечь вершину с минимальным ключом. В процессе выполнения процедуры это значение этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время O<tex>\Theta(\log n)</tex>, поскольку каждая из операций, которые используется в реализации, работают за <tex>\Theta(lgn\log n)</tex>.

Binomial_Heap_Delete'''function''' delete(H: '''BinomialHeap''', x: '''Node'''): Binomial_Heap_Decrease_KeydecreaseKey(H, x, -<tex>-\infty</tex>)<font color = "green">// уменьшение ключа до минимально возможного значения </font> Binomial_Heap_Extract_MinextractMin(H) <font color = "green">// удаление "всплывшего" элемента </font>

=== Персистентность ===Биноминальную кучу можно сделать [[Персистентные структуры данных|персистентной]] при реализации на односвязных списках<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. 538— ISBN 5-558.8489-0857-4 [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных‏‎]]