Изменения

'''Биномиальное Биномиальная куча''' (англ. ''binomial heap'') представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:*каждое биномиальное дерево в куче подчиняется свойству '''[[Двоичная куча|неубывающей кучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей кучи дерево ),*для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <tex>k</tex>.}} == Представление биномиальных куч ==Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей:*<tex>key</tex>B_k{{---}} ключ (вес) элемента,*<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>, то есть куча не содержит элементов. === getMinimum ===Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет). Так как корней в этом списке не более <tex>\lfloor \log n \rfloor + 1</tex>, то операция выполняется за <tex>O(\log n)</tex>. При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключом <tex>1</tex>. [[Файл:binHeapExample1_1.png|370px]] При использовании указателя на биномиальное дерево, определяемое которое содержит минимальный элемент, время для каждого этой операции может быть сведено к <tex>k = 0, O(1)</tex>. Указатель должен обновляться при выполнении любой операции, 2, кроме <tex>\mathrm{getMinimum}</tex>. Это может быть сделано за <tex>O(\dots log n)</tex> следующим образом, не ухудшая время работы других операций. === merge ===Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций. Вот в чем состоит ее суть: пусть есть две биномиальные кучи с <tex>B_0H</tex> и <tex>H'</tex>. Размеры деревьев в кучах соответствуют двоичным числам <tex>m</tex> и <tex>n</tex>, то есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев <tex>B_{k- 1}</tex> в дерево <tex>B_{k}</tex>. Надо только посмотреть, состоящее в каком из сливаемых деревьев корень меньше, и считать его верхним (пример работы для одного случая приведен на рисунке справа; в другом случае подвешиваем наоборот). [[Файл:helpBinaryHeapBoris.png|Пример слияние двух деревьев одного узла высоты 0порядка]] Работа этой процедуры начинается с соединения корневых списков куч в единый список, в котором корневые вершины идут в порядке неубывания их степеней. В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть состоит операция выполняется за <tex>\Omega(\log n)</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[curH] = curH.sibling tmp = curH.sibling curH.sibling = curH.sibling.child curH = tmp '''continue''' curH = curH.sibling '''return''' H</code> === 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(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 извлечения минимума]] <code> '''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 = x.sibling H' = ''null'' <font color = "green">//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на ''null'':</font> curx = x.child H'.head = x.child '''while''' curx != ''null'' p[curx] = ''null'' <font color = "green">// меняем указатель на родителя узла curx </font> curx = curx.sibling <font color = "green">// переход к следующему ребенку </font> H = merge(H, H') <font color = "green">// слияние нашего дерева с деревом H' </font> '''return''' x</code> === decreaseKey ===Следующая процедура уменьшает ключ элемента <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» как в обычной куче. Процедура выполняется за время <tex>B_\Theta(\log n)</tex>, поскольку глубина вершины <tex>x</tex> в худшем случае есть <tex>\Theta(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх. <code> '''function''' decreaseKey(H : '''BinomialHeap''', x : '''Node''', k: '''int'''): '''if''' k > key[x] <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, пока это значение меньше значения в родительской вершине </font> swap(key[y], key[z]) y = z z = p[y]</code> Пример работы процедуры проиллюстрирован на рисунке (<tex>y</tex> {{--1-}} уменьшаемый элемент, <tex>z</tex> {{---}} его предок). [[Файл:binHeapExample3_2.png|370px]] === delete ===Удаление ключа сводится к операциям <math>\mathrm {decreaseKey}</math> и <math>\mathrm {extractMin}</math>: сначала нужно уменьшить ключ до минимально возможного значения, а затем извлечь вершину с минимальным ключом. В процессе выполнения процедуры этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>\Theta(\log n)</tex>, поскольку каждая из операций, которые используется в реализации, работают за <tex>\Theta(\log n)</tex>. <code> '''function''' delete(H : '''BinomialHeap''', x : '''Node'''): decreaseKey(H, x, <tex>-\infty</tex>) <font color = "green">// уменьшение ключа до минимально возможного значения </font> extractMin(H) <font color = "green">// удаление "всплывшего" элемента </font></code> === Персистентность ===Биноминальную кучу можно сделать [[Персистентные структуры данных|персистентной]] при реализации на односвязных списках<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. — ISBN 5-8489-0857-4 [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных‏‎]]