Изменения

|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то есть степень корня больше степени остальных вершин, 3не будет нарушаться.

'''Свойства биномиальных деревьев. '''{{УтверждениеБиномиальное дерево |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="1center"bgcolor=#EEEEFF ! Операция |makeHeap| Время работы |-align="center" bgcolor=#FFFFFF |<tex>\Theta(1)mathrm{insert}</tex> |- |insert |<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> |} === makeHeap ===Для создания пустой биномиальной пирамиды процедура makeBinomialHeap просто выделяет память и возвращает объект Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H, где .head[</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H] .head = null</tex>, то есть пирамида куча не содержит элементов.

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

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

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

[[Файл<code> '''BinomialHeap''' merge(H1 : '''BinomialHeap''', H2 : '''BinomialHeap'''):Example5 '''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.jpg]degree p[curH]= curH.sibling tmp = curH.sibling curH.sibling = curH.sibling.child curH = tmp '''continue''' curH = curH.sibling '''return''' H</code>

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

'''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

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

[[Файл:Example6binHeapExample3_2.jpgpng|600px370px]]

Удаление ключа сводится к двум предыдущим операциям<math>\mathrm {decreaseKey}</math> и <math>\mathrm {extractMin}</math>: мы уменьшаем сначала нужно уменьшить ключ до минимально возможного значения, а затем удаляем извлечь вершину с минимальным ключом. В процессе выполнения процедуры это значение этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>O\Theta(\log n)</tex>, поскольку каждая из операций, которые используется в реализации, работают за <tex>\Theta(\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://enwww.wikipedialektorium.orgtv/wikilecture/Binomial_heap Wikipedia - Binomial heap?id=14234 Лекция А.С. Станкевича по приоритетным очередям]* Томас Х. Кормен Т, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ. — 2-е изд.— М.: «Вильямс», 2007. Страницы 538— с. 538—558. — ISBN 5-8489-0857-558.4 [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных‏‎]]