Изменения

|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" |Make_Heap |этом списке не более <tex>\Theta(1)</tex> |- |Insert |<tex>O(lfloor \log(n))\rfloor + 1</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>1</tex>.

[[Файл:binHeapExample1_1.png|370px]] При использовании указателя на биномиальное дерево, которое содержит минимальный элемент, время для этой операции может быть сведено к <tex>O(1)</tex>. Указатель должен обновляться при выполнении любой операции, кроме <tex>\mathrm{getMinimum}</tex>. Это может быть сделано за <tex>O(\log n)</tex>, не ухудшая время работы других операций. === Minimum merge ===Для нахождения минимального элемента надо найти элемент Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций. Вот в списке корней чем состоит ее суть: пусть есть две биномиальные кучи с минимальным значением (предполагается<tex>H</tex> и <tex>H'</tex>. Размеры деревьев в кучах соответствуют двоичным числам <tex>m</tex> и <tex>n</tex>, что ключейто есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, равных иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев <tex>B_{k-1}</tex>\inftyв дерево <tex>B_{k}</tex>. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, нети считать его верхним (пример работы для одного случая приведен на рисунке справа; в другом случае подвешиваем наоборот). [[Файл:helpBinaryHeapBoris.png|Пример слияние двух деревьев одного порядка]]

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

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

Для этого нам надо сначала слить списки корней <texcode>H_1 '''BinomialHeap''' merge(H1 : '''BinomialHeap''', H_2H2 : '''BinomialHeap'''): '''if''' H1 == ''null'' '''return''' H2 '''if''' H2 == ''null'' '''return''' H1 H.head = ''null'' <font color = "green"> // H {{---}} результат слияния </texfont> 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[curH] = curH.sibling tmp = curH.sibling curH.sibling = curH.sibling. На каждом шаге нам надо расмотреть несколько случаевchild curH = tmp '''continue''' curH = curH.sibling '''return''' H</code>

* Рассматриваемое дерево и следующее за ним имеют разные степени (случай === insert ===Чтобы добавить новый элемент в биномиальную кучу нужно создать биномиальную кучу <tex>H''a'' на рисунке). Ситуация тривиальна и не требует никаких действий. Переходим к следующему шагу.* Текущее дерево и его два ближаших соседа справа (то есть те</tex> с единственным узлом, содержащим этот элемент, которые встретятся на последующих итерациях) имеют одинаковые степени за время <tex>O(случай ''b'' на рисунке1). Эта ситуация хоть </tex> и не тривиальна, но объединить ее следует оставить для следующего шага.* Если степень текущего и последующего деревьев одинакова с биномиальной кучей <tex>H</tex> за <tex>O(случай ''c-d'' на рисунке\log n)</tex>, то нам следует объединить их так как в новое данном случае куча <tex>H'</tex> содержит лишь одно дерево (сделав корнем вершину того дерева, чей ключ наименьший), степень которого будет на единицу больше той, что была ранее.

Пример пирамиды до Union Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и после:возвращает указатель на извлеченный узел.

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

=== Inset ===Необходимо просто создать биномиальную пирамиду Процедура выполняется за время <tex>H'\Theta(\log n)</tex> с одним узлом за время , поскольку всего в списке <tex>O\Theta(1\log n)</tex> и объединяет ее корней биномиальных деревьев. И всего у найденного дерева <tex> k </tex> порядка (с биномиальной пирамидой Нминимальным значением ключа) ровно <tex> k </tex> детей, содержащей то сложность перебора этих детей будет тоже <tex>\Theta(\log n узлов, )</tex>. А процесс слияния выполняется за время <tex>O\Omega(\logn)</tex>. Таким образом, операция выполняется <tex>\Theta(\log n))</tex>.

=== Extract_Min ===Приведенная ниже процедура извлекает узел с минимальным ключок из биномиальной кучи и возвращает указатель на извлеченный узел[[Файл:BinHeapExampleNew31.png|700px|Примеp извлечения минимума]]

Binomial_Heap_Extract_Min '''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 = Make_Binomial_Heap()x.sibling Обращение порядка связанного списка дочерних узлов х H' = ''null'' <font color = "green">//построение кучи детей вершины x,при этом изменяем предка соответствующего ребенка на ''null'':</font> установка поля р каждого дочернего узла Н равным NILcurx = x.child присвоение указателю H'.head= x.child '''while''' curx != ''null'' p[Hcurx] = ''null''] адреса заголовка <font color = "green">// меняем указатель на родителя узла curx </font> curx = curx.sibling <font color = "green">// переход к следующему ребенку </font> получающегося списка H = Binomial_Heap_Unionmerge(H, H') <font color = "green">// слияние нашего дерева с деревом H' </font> '''return ''' x

Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи. Все действия выполняются за время O(lgn), так что общее время работы процедуры есть O(lgn) === 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 [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных‏‎]]