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

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

2012-03-05T18:12:23Z

109.188.196.221: /* Источники */

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

Пример биномиального дерева для k = 0, 2, 3.

[[Файл:Example.jpg|325px|]]

'''Свойства биномиальных деревьев. '''
Биномиальное дерево <tex>B_k</tex> с n вершинами:
*имеет <tex>2^k</tex> узлов;
*имеет высоту k;
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
*имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева;
*максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\log(n)</tex>.

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

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

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

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

----

Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.
{| border="1"
|makeHeap
|<tex>\Theta(1)</tex>
|-
|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>
|}

=== makeHeap ===
Для создания пустой биномиальной пирамиды процедура makeBinomialHeap просто выделяет память и возвращает объект H, где head[H] = null, то есть пирамида не содержит элементов.

=== getMinimum ===
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).

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

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

[[Файл:Example2.jpg|300px]]

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

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

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

[[Файл:Example3.jpg|300]]

Пример пирамиды до merge и после:

[[Файл:Example5.jpg]]

=== insert ===
Необходимо просто создать биномиальную пирамиду <tex>H'</tex> с одним узлом за время <tex>O(1)</tex> и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время <tex>O(\log(n))</tex>.

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

<code>
extractMin(H)
поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н
H' = Make_Binomial_Heap()
Обращение порядка связанного списка дочерних узлов х,
установка поля р каждого дочернего узла Н равным NIL
присвоение указателю head[H'] адреса заголовка
получающегося списка
H = Binomial_Heap_Union(H, H')
return x
</code>

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

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

<code>
Binomial_Heap_Decrease_Key(H, x, k)
if k > key[x] then
return
key[x] = k
y = x
z = p[y]
while (z <tex>\ne</tex> NIL and key[y] < key[z]) do
swap(key[y], key[z])
y = z
z = p[y]
</code>

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

[[Файл:Example6.jpg|600px]]

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

<code>
Binomial_Heap_Delete(H, x)
Binomial_Heap_Decrease_Key(H, x, -<tex>\infty</tex>)
Binomial_Heap_Extract_Min(H)
</code>

== Источники ==
----
* [http://www.intuit.ru/department/algorithms/dscm/7/ INTUIT.ru - Биномиальные кучи]
* [http://en.wikipedia.org/wiki/Binomial_heap Wikipedia - Binomial heap]
* Кормен Т. Алгоритмы: построение и анализ. 2-е изд., 2007. Страницы 538-558.

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

2012-03-05T18:05:04Z

109.188.196.221: /* Операции над биномиальными пирамидами */

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

Пример биномиального дерева для k = 0, 2, 3.

[[Файл:Example.jpg|325px|]]

'''Свойства биномиальных деревьев. '''
Биномиальное дерево <tex>B_k</tex> с n вершинами:
*имеет <tex>2^k</tex> узлов;
*имеет высоту k;
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
*имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева;
*максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\log(n)</tex>.

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

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

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

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

----

Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.
{| border="1"
|makeHeap
|<tex>\Theta(1)</tex>
|-
|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>
|}

=== makeHeap ===
Для создания пустой биномиальной пирамиды процедура makeBinomialHeap просто выделяет память и возвращает объект H, где head[H] = null, то есть пирамида не содержит элементов.

=== getMinimum ===
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).

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

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

[[Файл:Example2.jpg|300px]]

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

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

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

[[Файл:Example3.jpg|300]]

Пример пирамиды до merge и после:

[[Файл:Example5.jpg]]

=== insert ===
Необходимо просто создать биномиальную пирамиду <tex>H'</tex> с одним узлом за время <tex>O(1)</tex> и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время <tex>O(\log(n))</tex>.

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

<code>
extractMin(H)
поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н
H' = Make_Binomial_Heap()
Обращение порядка связанного списка дочерних узлов х,
установка поля р каждого дочернего узла Н равным NIL
присвоение указателю head[H'] адреса заголовка
получающегося списка
H = Binomial_Heap_Union(H, H')
return x
</code>

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

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

<code>
Binomial_Heap_Decrease_Key(H, x, k)
if k > key[x] then
return
key[x] = k
y = x
z = p[y]
while (z <tex>\ne</tex> NIL and key[y] < key[z]) do
swap(key[y], key[z])
y = z
z = p[y]
</code>

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

[[Файл:Example6.jpg|600px]]

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

<code>
Binomial_Heap_Delete(H, x)
Binomial_Heap_Decrease_Key(H, x, -<tex>\infty</tex>)
Binomial_Heap_Extract_Min(H)
</code>

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