Изменения

|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>, нет). [[Файл:binHeapExample1_1.png|370px]]

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

При вызове этой процедуры для === merge ===Эта операция, соединяющая две биномиальные кучив одну, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем 1используется в качестве подпрограммы большинством остальных операций.

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

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

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

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

Binomial_Heap_Insert '''BinomialHeap''' merge(HH1 : '''BinomialHeap''', xH2 : '''BinomialHeap'''): '''if''' H1 == ''null'' '''return''' H2 '''if''' H2 == ''null'' '''return''' H1 H.head = ''null'' <font color = Make_Binpmial_Heap"green"> // H {{---}} результат слияния </font> p[x] 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 = NILcurH2.sibling child[x] '''if''' curH1 == ''null'' '''while''' curH2 != ''null'' curH.sibling = curH2 curH2 = NILcurH2.sibling '''else''' '''while''' curH1 != ''null'' curH.sibling = curH1 curH1 = curH1.sibling[x] curH = H.head <font color = NIL"green"> // объединение деревьев одной степени </font> '''while''' curH.sibling != ''null'' '''if''' curH.degree == curH.sibling.degree p[xcurH] = 0curH.sibling tmp = curH.sibling head[H curH.sibling = curH.sibling.child curH = tmp '''continue'''] curH = xcurH.sibling '''return''' H = Binomial_Heap_Union(H, 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(lg1)</tex>.* Пусть <tex>H'</tex> {{---}} куча детей найденного корня. При этом мы для каждого из ребенка устанавливаем указатель на предка равным <tex>null</tex>. После этого сливаем кучу <tex>H'</tex> c <tex>H</tex> за <tex>\Omega(\log n))</tex>.

=== Extract_Min ===Приведенная ниже процедура извлекает узел Процедура выполняется за время <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 извлечения минимума]]

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 [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных‏‎]]