Биномиальная куча

2013-06-09T20:48:00Z

94.25.229.122: уменЬшение во(х->з)можного

[[Файл:binHeapExample.png|thumb|325px|Пример биномиальных деревьев <tex>B_0, B_2, B_3</tex>]]
= Биномиальное дерево =

{{Определение
|definition =
'''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{---}} дерево, состоящее из одного узла; <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>{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>{k\choose i} + {k\choose {i - 1}}</tex>, так как от подвешенного дерева в дерево порядка <tex>k+1</tex> нам пришли узлы глубины <tex>i-1</tex>. То для <tex>i</tex>-го уровня дерева <tex>B_{k+1}</tex> количество узлов <tex>{k\choose i} + {k\choose {i - 1}} ={{k + 1}\choose i} </tex>. Переход доказан, то биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет ровно <tex>{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>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться.

}}

{{Утверждение
|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(\log(n))</tex>, то степень произвольного узла не более <tex>\log(n)</tex>.
}}

= Биномиальная куча=
{{Определение
|definition=
'''Биномиальная куча ''' представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:
*Каждое биномиальное дерево в куче подчиняется свойству '''[[Двоичная куча|неубывающей кучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей кучи дерево).
*Для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <tex>k</tex>.}}

== Представление биномиальных куч ==
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей:
*<tex>key</tex> {{---}} ключ (вес) элемента;
*<tex>parent</tex> {{---}} указатель на родителя узла;
*<tex>child</tex> {{---}} указатель на левого ребенка узла;
*<tex>sibling</tex> {{---}} указатель на правого брата узла;
*<tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).

Корни деревьев, их которых состоит куча, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в возрастающем порядке.
Доступ к куче осуществляется ссылкой на первый корень в списке корней.

== Операции над биномиальными кучами==

Рассмотрим операции, которые можно производить с биномиальной кучей. Время работы указано в таблице:
{| border="1"
|insert
|<tex>O(\log(n))</tex>
|-
|getMinimum
|<tex>O(\log(n))</tex>
|-
|extractMin
|<tex>\Theta(\log(n))</tex>
|-
|merge
|<tex>\Omega(\log(n))</tex>
|-
|decreaseKey
|<tex>\Theta(\log(n))</tex>
|-
|delete
|<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]]

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

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

[[Файл:helpBinaryHeapBoris.png|Пример слияние двух деревьев одного порядка]]

Работа этой процедуры начинается с соединения корневых списков куч в единый список, в котором корневые вершины идут в порядке неубывания их степеней.

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

<code>
Node merge(H1, H2)
if H1 == null
return H2

if H2 == null
return H1

// H - результат слияния
H.head = null

// Слияние корневых списков
curH = H.head
curH1 = H1.head
curH2 = H2.head
while curH1 != null && 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
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)
//поиск корня х с минимальным значением ключа в списке корней Н:
min = <tex>\infty</tex>
x = null
xBefore = null

curx = H.head
curxBefore = null
while curx != null
// релаксируем текущий минимум
if curx.key < min
min = curx.key
x = curx
xBefore = curxBefore

curxBefore = curx
curx = curx.sibling

//удаление найденного корня x из списка корней деревьев кучи
if (xBefore == null)
H.head = x.sibling
else
xBefore.sibling = x.sibling

//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на null:
H' = null
curx = x.child
H'.head = x.child
while curx != null
// меняем указатель на родителя узла curx
p[curx] = null
// переход к следующему ребенку
curx = curx.sibling

// слияние нашего дерева с деревом H'
H = merge(H, H')
return x
</code>

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

<code>
void decreaseKey(H, x, k)
// проверка на то, что текущий ключ не меньше передаваемого ключа k
if k > key[x]
return
key[x] = k
y = x
z = p[y]
//поднимаем текущий элемент x с новым ключом k, пока
//это значение меньше значения в родительской вершине
while z != null and key[y] < key[z]
swap(key[y], key[z])
y = z
z = p[y]

</code>

Пример работы процедуры проиллюстрирован на рисунке (<tex>y</tex> {{---}} уменьшаемый элемент, <tex>z</tex> {{---}} его предок).

[[Файл:binHeapExample3_2.png|370px]]

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

<code>
void delete(H, x)
//уменьшение ключа до минимально возможного значения
decreaseKey(H, x, <tex>-\infty</tex>)
//удаление "всплывшего" элемента
extractMin(H)
</code>

== Источники ==
* [http://www.intuit.ru/department/algorithms/dscm/7/ Биномиальные кучи — INTUIT.ru]
* [http://en.wikipedia.org/wiki/Binomial_heap Binomial heap — Wikipedia]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538—558. — ISBN 5-8489-0857-4

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]

Викиконспекты - Вклад участника [ru]

Биномиальная куча