Изменения

|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>.}} = Биномиальная куча=

'''Биномиальная пирамида 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*''key'' ||<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>*''parent'' {{|---}} указатель на родителя узла;align="center" bgcolor=#FFFFFF*''child'' |<tex>\mathrm{{---delete}</tex>||<tex>\Theta(\log n)</tex>|} указатель на левого ребенка узла;*''sibling'' Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на правого брата узла;*''degree'' {{---}} степень узла (количество дочерних узлов данного узла)корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов.

Доступ к куче осуществляется ссылкой на самое левое поддерево. Корни деревьев=== getMinimum ===Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, из которых составлена кучачто ключей, оказываются организованными с помощью поля ''sibling'' в так называемый корневой односвязный списокравных <tex>\infty</tex>, нет).

== Операции над биномиальными пирамидами ==Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их верхние асимптотические оценки показаны Так как корней в таблице.{| border="1" |Make_Heap |этом списке не более <tex>\Theta(1)</tex> |- |Insert |<tex>O(lfloor \lg(log n))\rfloor + 1</tex> |- |Minimum |, то операция выполняется за <tex>O(\lg(n))</tex> |- |Extract_Min |<tex>\Theta(\lg(n))</tex> |- |Union |<tex>\Omega(\lg(n))</tex> |- |Decrease_Key |<tex>\Theta(\lg(log n))</tex> |- |Delete |<tex>\Theta(\lg(n))</tex> |}=== Make_Heap ===Для создания пустой биномиальной приамиды процедура Make_Binomial_Heap просто выделяет память и возвращает объект H, где head[H] = nil, то есть пирамида не содержит элементов.

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

<code> Binomial_Yeap_Minimum(H) y = NIL x = head[H] min = <tex>\infty</tex> while x <tex>\ne</tex> NIL do if key[xФайл:binHeapExample1_1.png|370px] < min then y = x x = sibling[x] return y

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

=== Union merge ===

Процедура Binomial_Heap_Union многократно связывает Вот в чем состоит ее суть: пусть есть две биномиальные деревья кучи с корнями одинаковой степени<tex>H</tex> и <tex>H'</tex>. Приведенная далее процедура связывает дерево Размеры деревьев в кучах соответствуют двоичным числам <tex>m</tex> и <tex>B_kn</tex> с корнем y с деревом , то есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев <tex>B_{k-1}</tex> в дерево <tex>B_{k}</tex>. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, и считать его верхним (пример работы для одного случая приведен на рисунке справа; в другом случае подвешиваем наоборот). [[Файл:helpBinaryHeapBoris.png|Пример слияние двух деревьев одного порядка]] Работа этой процедуры начинается с корнем zсоединения корневых списков куч в единый список, делая z родительским узлом для yв котором корневые вершины идут в порядке неубывания их степеней. В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, после чего узел z становится корнем дерева то есть операция выполняется за <tex>B_k\Omega(\log n)</tex>.   

Binomial_Link '''BinomialHeap''' merge(yH1 : '''BinomialHeap''', zH2 : '''BinomialHeap'''): p[y] '''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 = zcurH2.sibling '''else''' '''while''' curH1 != ''null'' curH.sibling[y] = child[z]curH1 curH1 = curH1.sibling child[z] curH = H.head <font color = y"green"> // объединение деревьев одной степени </font> '''while''' curH.sibling != ''null'' '''if''' curH.degree== curH.sibling.degree p[zcurH]++= curH.sibling tmp = curH.sibling curH.sibling = curH.sibling.child curH = tmp '''continue''' curH = curH.sibling '''return''' H

=== insert ===Чтобы добавить новый элемент в биномиальную кучу нужно создать биномиальную кучу <tex>H'</tex> с единственным узлом, содержащим этот элемент, за время <tex>O(1)</tex> и объединить ее с биномиальной кучей <tex>H</tex> за <tex>O(\log n)</tex>, так как в данном случае куча <tex>H'</tex> содержит лишь одно дерево. === extractMin === Приведенная далее ниже процедура сливает биномиальные извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел.  Рассмотрим пошагово алгоритм:* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <tex>H_1B_k</tex>. Время работы этого шага алгоритма <tex>\Theta(\log n)</tex>.* Удаляем дерево <tex>B_k</tex> из кучи <tex>H</tex>. Иными словами, H_2удаляем его корень из списка корней кучи. Это можно сделать за время <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>H_1порядка (с минимальным значением ключа) ровно <tex> k </tex> детей, H_2то сложность перебора этих детей будет тоже <tex>\Theta(\log n)</tex> удаляются. Процедура Binomial_Heap_Merge сливает списки корней А процесс слияния выполняется за <tex>\Omega(\log n)</tex>H_1. Таким образом, H_2операция выполняется <tex>\Theta(\log n)</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. [[Файл:BinHeapExampleNew31.png|700px|Примеp извлечения минимума]]

  Binomial_Heap_Union '''Node''' extractMin(<tex>H_1, H_2</tex>) H = Make_Binomial_Heap(: '''BinomialHeap''') head[H] : <font color = Binomial_Heap_Merge(<tex"green">H_1, H_2//поиск корня х с минимальным значением ключа в списке корней Н: </texfont>) delete min = <tex>H_1, H_2\infty</tex> //удаление объектов, но не списков, на которые они указывают if head[H] x = NIL''null'' then return H prex_x xBefore = NIL''null'' x curx = H.head[H] next_x curxBefore = sibling[x]''null'' '''while next_x ''' curx != ''null'' '''if''' curx.key <texmin <font color = "green">\ne// релаксируем текущий минимум </texfont> NIL do min = curx.key x = curx xBefore = curxBefore curxBefore = curx curx = curx.sibling '''if (degree[x] ''' xBefore == ''null'' <texfont color = "green">\ne</tex> degree[next_x]) or (sibling[next_x] <tex>\ne/удаление найденного корня x из списка корней деревьев кучи</texfont> NIL and degree[sibling[next_x]] = degree[x]) then prex_x H.head = x.sibling '''else if key[x] <= key[next_x] then''' xBefore.sibling[= x] = .sibling[next_x] Binomial_Link(next_x H' = ''null'' <font color = "green">//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на ''null'':</font> curx = x).child else H'.head = x.child if prev_x '''while''' curx != NIL then''null'' head p[Hcurx] = next_x''null'' <font color = "green">// меняем указатель на родителя узла curx </font> else curx = curx.sibling[prev_x] <font color = next_x"green">// переход к следующему ребенку </font> Binomial_Link H = merge(xH, next_xH') x <font color = next_x"green">// слияние нашего дерева с деревом H' </font> next_x = sibling['''return''' x]

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

Binomial_Heap_Insert '''function''' decreaseKey(H: '''BinomialHeap''', x: '''Node''', k : '''int'''): H '''if''' = Make_Binpmial_Heap pk > key[x] <font color = NIL"green">// проверка на то, что текущий ключ x не меньше передаваемого ключа k </font> child '''return''' key[x] = NILk sibling y = x z = p[xy] '''while''' z != NIL degree''null'' '''and''' key[xy] = 0 head< key[H'z] <font color = "green">// поднимаем xс новым ключом k, пока это значение меньше значения в родительской вершине </font> H = Binomial_Heap_Union swap(Hkey[y], H'key[z]) y = z z = p[y]

Процедура просто создает биномиальную пирамиду H' с одним узлом за время ОПример работы процедуры проиллюстрирован на рисунке (1) и объединяет ее с биномиальной пирамидой Н<tex>y</tex> {{---}} уменьшаемый элемент, содержащей n узлов, за время О(lg(n)<tex>z</tex> {{---}} его предок). [[Файл:binHeapExample3_2.png|370px]]

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

Binomial_Heap_Extract_Min'''function''' delete(H) поиск корня х с минимальным значением ключа в списке корней Н: '''BinomialHeap''', и удаление х из корней Н Hx : '''Node''' = Make_Binomial_Heap() Обращение порядка связанного списка дочерних узлов х,: установка поля р каждого дочернего узла Н равным NIL присвоение указателю head[decreaseKey(H'] адреса заголовка , x, <tex>-\infty</tex>) <font color = "green">// уменьшение ключа до минимально возможного значения </font> получающегося списка H = Binomial_Heap_UnionextractMin(H, H') return x <font color = "green">// удаление "всплывшего" элемента </font>

Поскольку минимальный элемент находится === Персистентность ===Биноминальную кучу можно сделать [[Персистентные структуры данных|персистентной]] при реализации на односвязных списках<ref>[https://github.com/kgeorgiy/okasaki/tree/master/Okasaki/Chapter3 Github {{---}} реализация на Haskell]</ref>. Для этого будем хранить список корней в корневом спискепорядке возрастания ранга, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размераа детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который надо объединить является головой списка детей, но ребенок не будет знать родителя. Односвязанные списки хороши с оставшейся частью кучиточки зрения функционального программирования, так как голова списка не будет достижима из потомков. Все действия выполняются за время O(lgn)Тогда при добавлениии новой версии в голову или удалении объявляя другую вершину новой головой мы не будем терять старые версии, которые останутся на месте, так как фактически односвязный список с операциями на голове это [[Персистентный стек|персистентный стек]], который является полностью персистентной функциональной структурой. При этом каждая версия будет поддерживать возможность изменения, что является полным уровнем персистентности. Также поддерживается операция <tex>\mathrm {merge}</tex> для всех версий биномиальных куч, что общее время работы процедуры есть O(lgn)позволяет получать новую версию путём сливания старых. Это добавляет конфлюэнтный уровень персистентности.

=== Decrease_Key =См. также ==Следующая процедура уменьшает ключ элемента х биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время O(lgn), поскольку глубина вершины х есть O(lgn) (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.* [[Двоичная куча]]* [[Фибоначчиева куча]]* [[Левосторонняя куча]]* [[Куча Бродала-Окасаки]]

<code> Binomial_Heap_Decrease_Key(H, x, k) if k > key[x] then return key[x] = k y = x z Примечания= p[y] while (z <tex>\ne</tex> NIL and key[y] < key[z]) do swap(key[y], key[z]) y = z z = p[y]</code>

<references />=== Delete Источники информации ==* [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. — с. Процедура выполняется за время O(lgn)538—558.— ISBN 5-8489-0857-4