Изменения

'''Биномиальное дерево <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>2^0 = 1k </tex> узелусловие верно, то при любом <tex>k</tex>докажем, дерево порядка что для <tex> k+ 1</tex> имеет <tex>2^k</tex> узлов.это также верно:

*имеет высоту Так как в дереве порядка <tex>k+1</tex>;В силу тоговдвое больше узлов, что с увеличением чем в дереве порядка дерева на <tex>1k</tex>, мы подвешиваем к текущему дереву то дерево того же порядка, то высота получившегося в результате слияния дерева увеличивается на <tex>k+1</tex>. Изначально имеем высоту имеет <tex>2^0 k \cdot 2 = 2^{k+1}</tex>узлов. Переход доказан, то при любом биномиальное дерево <tex>kB_k</tex>, дерево порядка с <tex> kn</tex> вершинами имеет высоту <tex>2^k</tex>узлов.}}

*имеет ровно {{Утверждение|statement=Биномиальное дерево <tex>B_k</tex> с <tex>{k\choose i}n</tex> узлов на высоте вершинами имеет высоту <tex>i = 0, 1, 2, \dotsk</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>{k\choose i} + {k\choose {i - 1}}</tex>. Переход доказан, т.к. от подвешенного дерева в то биномиальное дерево порядка <tex>k+1B_k</tex> нам пришли узлы глубины с <tex>i-1n</tex>. То для вершинами имеет высоту <tex>i</tex> уровня дерева <tex>B_{k+1}</tex> количество узлов <tex>{k\choose i} + {k\choose {i - 1}} ={{k + 1}\choose i} </tex>. То свойство доказано.

*максимальная степень произвольного узла в биномиальном дереве {{Утверждение|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n узлами равна </tex> вершинами имеет ровно <texdpi = "165">k\log(n)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>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться. }} {{Утверждение|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(\log(n))</tex>, то степень произвольного узла не более <tex>\log(n)</tex>.}}

'''Биномиальная пирамида куча''' ([[Двоичная куча|куча]]) англ. ''binomial heap'' {{---}} ) представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам :*Каждое каждое биномиальное дерево в пирамиде куче подчиняется свойству '''[[Двоичная куча|неубывающей пирамидыкучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей пирамиды кучи дерево).,*Для для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <tex>k</tex>.}}

Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:*<tex>key</tex> {{---}} ключ (вес) элемента;,*<tex>parent</tex> {{---}} указатель на родителя узла;,*<tex>child</tex> {{---}} указатель на левого ребенка узла;,*<tex>sibling</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>, то есть пирамида куча не содержит элементов.

Асимптотика этой операции получается из того, что Так как корней в этом списке не более <tex>\lfloor \log(n) \rfloor + 1</tex>, то операция выполняется за <tex>O(\log n)</tex>. При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключом <tex>1</tex>.

При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем <tex>1</tex>[[Файл:binHeapExample1_1.png|370px]]

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

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

Если текущий корень имеет разные степени с следующим за ним, то ничего с ним не делаем и продолжаем цикл[[Файл:helpBinaryHeapBoris. Это дерево в итоге останется в таком виде в конечной куче(случай <tex>a</tex> на рисунке). Если же степень текущего элемента равна степеням последующих png|Пример слияние двух вершин(это может случится в том случае, если в каждом из двух исходных деревьев был корень с этой степенью и еще одно дерево образовалось в ходе текущего слияния деревьев; причем более, чем трех корней с одинаковой степенью быть не может по нашему алгоритму и начальным условиям), то оставим это дерево нетронутым, но после на следующем шаге сольем два других дерева с этой степенью. Иными словами переходим к следующей вершине, в которой уже будет происходить слияние(случай <tex>b</tex> на рисунке). В последнем случае мы имеем лишь две подряд вершины с одинаковой степенью корней. В этой ситуаций мы дерево с большим значением в корне вершины подвешиваем к дерево с меньшим значением в корне (случаи <tex> c, d</tex> на рисунке).одного порядка]]

ПримРабота этой процедуры начинается с соединения корневых списков куч в единый список, в котором корневые вершины идут в порядке неубывания их степеней. на рисунке <tex>sibling[next-x]</tex> {{---}} следующий элемент в списке для <tex>next-x</tex>

Пример пирамиды до <code> '''BinomialHeap''' merge и после(H1 :'''BinomialHeap''', H2 : '''BinomialHeap'''): '''if''' H1 == ''null'' '''return''' H2 '''if''' H2 == ''null'' '''return''' H1 H.head = ''null'' <font color = "green"> // H {{---}} результат слияния </font> curH = H.head <font color = "green"> // слияние корневых списков </font> curH1 = 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[[Файл:Example5curH] = curH.sibling tmp = curH.sibling curH.sibling = curH.sibling.child curH = tmp '''continue''' curH = curH.jpg]]sibling '''return''' H</code>

Необходимо просто Чтобы добавить новый элемент в биномиальную кучу нужно создать биномиальную пирамиду кучу <tex>H'</tex> с одним единственным узлом , содержащим этот элемент, за время <tex>O(1)</tex> и объединяет объединить ее с биномиальной пирамидой кучей <tex>НH</tex>, содержащей за <tex>O(\log n)</tex> узлов, за время так как в данном случае куча <tex>O(\log(n))H'</tex>содержит лишь одно дерево.

Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел.  Рассмотрим пошагово алгоритм:* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <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 извлечения минимума]]

'''Node ''' extractMin(H: '''BinomialHeap''') { : <font color = "green">//поиск корня х с минимальным значением ключа в списке корней Н: </font> min = <tex>\infty</tex>; x = ''null;'' xBefore = ''null'' curx = H.head[H]; curxBefore = ''null'' '''while ''' curx <tex>\ne</tex> != ''null {'' '''if ''' curx.key < min { <font color = "green"> // релаксируем текущий минимум </font> min = curx.key; x = curx; } xBefore = curxBefore curxBefore = curx curx = curx.next; }sibling '''if''' xBefore == ''null'' <font color = "green"> //удаление найденного корня x из списка корней деревьев кучи</font> x H.prev.next head = x.next;sibling x'''else''' xBefore.next.prev sibling = x.prev; sibling H' = ''null'' <font color = "green">//добавление построение кучи детей элемента вершины x, при этом изменяем предка соответствующего ребенка на ''null'':</font> curx = x в кучу.child H' = null; curx .head = x.child; '''while ''' curx <tex>\ne</tex> != ''null {'' p[curx] = ''null; '' <font color = "green">// удаление элемента x из предков меняем указатель на родителя узла curx</font> head[H'] curx = curx;.sibling <font color = "green">// переход к следующему ребенку </font> H = merge(H, H'); <font color = "green">// слияние нашего дерева с текущим деревом H' curx = curx.sibling; }</font> '''return ''' x; } 

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

void '''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 != ''null'' '''and''' key[y] < key[z] <font color = "green">//поднимаем текущий элемент x с новым ключом k, пока //это значение меньше значения в родительской вершине while z <tex>\ne</texfont> null and key[y] < key[z] do { swap(key[y], key[z]); y = z; z = p[y]; } }

[[Файл:binHeapExample3binHeapExample3_2.png|400px370px]]

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

void '''function''' delete(H: '''BinomialHeap''', x: '''Node''') { //уменшение ключа до минимально вохможного значения: decreaseKey(H, x, -<tex>-\infty</tex>);<font color = "green">// уменьшение ключа до минимально возможного значения </font> extractMin(H) <font color = "green">//удаление "всплывшего" элемента extractMin(H); }</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://enwww.wikipedialektorium.orgtv/wikilecture/Binomial_heap Binomial heap — Wikipedia?id=14234 Лекция А.С. Станкевича по приоритетным очередям]* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538-558538—558. — ISBN 5-8489-0857-4 [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных‏‎]]