Биномиальная куча — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Операции над биномиальными кучами)
м (rollbackEdits.php mass rollback)
 
(не показана 181 промежуточная версия 16 участников)
Строка 1: Строка 1:
 
+
[[Файл:binHeapExample.png|thumb|325px|Пример биномиальных деревьев <tex>B_0, B_2, B_3</tex>]]
 
= Биномиальное дерево =
 
= Биномиальное дерево =
  
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{---}} дерево, состоящее из одного узла высоты <tex>0</tex>, то есть состоит из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.
+
'''Биномиальное дерево <tex>B_k</tex>''' (англ. ''binomial tree'') {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{---}} дерево, состоящее из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанных вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.
 
}}
 
}}
  
[[Файл:binHeapExample.png|thumb|325px|Пример биномиальных деревьев <tex>B_0, B_2, B_3</tex>]]
 
  
 
== Свойства биномиальных деревьев ==
 
== Свойства биномиальных деревьев ==
  
Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами:
+
{{Утверждение
*имеет <tex>2^k</tex> узлов;
+
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет <tex>2^k</tex> узлов.
 +
|proof=
 +
Докажем по индукции:
  
Так как в дереве порядка <tex>k+1</tex> вдвое больше узлов, чем в дереве порядка <tex>k</tex>, а в дереве нулевого порядка <tex>1 = 2^0</tex> узел, то дерево порядка <tex>k</tex> имеет <tex>2^k</tex> узлов.
+
База <tex>k = 1</tex> {{---}} верно. Пусть для некоторого <tex>k </tex> условие верно, то докажем, что для <tex>k + 1</tex> это также верно:
  
*имеет высоту <tex>k</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> узлов.
 +
}}
  
Так как в дереве порядка <tex>k+1</tex> высота больше на <tex>1</tex> (так как мы подвешиваем к текущему дереву дерево того же порядка), чем в дереве порядка <tex>k</tex>, а в дереве нулевого порядка высота <tex>0</tex> , то дерево порядка <tex>k</tex> имеет высоту <tex>k</tex>.
+
{{Утверждение
 +
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет высоту <tex>k</tex>.
 +
|proof=
 +
Докажем по индукции:
  
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
+
База <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>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>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>.
 +
}}
  
*имеет корень степени <tex>k</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>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться.
  
Так как в дереве порядка <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>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться.
+
}}
  
*максимальная степень произвольного узла в биномиальном дереве с <tex>n</tex> узлами равна <tex>\log(n)</tex>.
+
{{Утверждение
 
+
|statement=В биномиальном дереве <tex>B_k</tex> с <tex>n</tex> вершинами максимальная степень произвольного узла равна <tex>\log n</tex>.
Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Так как степень корня дерева порядка <tex>k</tex> равна <tex>k</tex>, а узлов в этом дереве <tex>n = 2^k</tex>, то прологарифмировав обе части получаем, что <tex>k=O(\log(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=
 
|definition=
'''Биномиальная пирамида ([[Двоичная куча|куча]]) ''' {{---}} представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:
+
'''Биномиальная куча''' (англ. ''binomial heap'') представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:
*Каждое биномиальное дерево в пирамиде подчиняется свойству '''неубывающей пирамиды''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей пирамиды дерево).
+
*каждое биномиальное дерево в куче подчиняется свойству '''[[Двоичная куча|неубывающей кучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей кучи дерево),
*Для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <tex>k</tex>.}}
+
*для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <tex>k</tex>.}}
  
 
== Представление биномиальных куч ==
 
== Представление биномиальных куч ==
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:
+
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей:
*<tex>key</tex> {{---}} ключ (вес) элемента;
+
*<tex>key</tex> {{---}} ключ (вес) элемента,
*<tex>parent</tex> {{---}} указатель на родителя узла;
+
*<tex>parent</tex> {{---}} указатель на родителя узла,
*<tex>child</tex> {{---}} указатель на левого ребенка узла;
+
*<tex>child</tex> {{---}} указатель на левого ребенка узла,
*<tex>sibling</tex> {{---}} указатель на правого брата узла;
+
*<tex>sibling</tex> {{---}} указатель на правого брата узла,
 
*<tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
 
*<tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
  
Корни деревьев, их которых состоит пирамида, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в неубывающем порядке.
+
Корни деревьев, из которых состоит куча, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в возрастающем порядке.
 
Доступ к куче осуществляется ссылкой на первый корень в списке корней.
 
Доступ к куче осуществляется ссылкой на первый корень в списке корней.
  
 
== Операции над биномиальными кучами==
 
== Операции над биномиальными кучами==
  
 
+
Рассмотрим операции, которые можно производить с биномиальной кучей. Время работы указано в таблице:
Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.
+
{| class="wikitable" style="width:10cm" border=1
{| border="1"
+
|+
|insert
+
|-align="center" bgcolor=#EEEEFF
|<tex>O(\log(n))</tex>
+
! Операция || Время работы
|-
+
|-align="center" bgcolor=#FFFFFF
|getMinimum
+
|<tex>\mathrm{insert}</tex>||<tex>O(\log n)</tex>
|<tex>O(\log(n))</tex>
+
|-align="center" bgcolor=#FFFFFF
|-
+
|<tex>\mathrm{getMinimum}</tex>||<tex>O(\log n)</tex>
|extractMin
+
|-align="center" bgcolor=#FFFFFF
|<tex>\Theta(\log(n))</tex>
+
||<tex>\mathrm{extractMin}</tex>||<tex>\Theta(\log n)</tex>
|-
+
|-align="center" bgcolor=#FFFFFF
|merge
+
|<tex>\mathrm{merge}</tex>||<tex>\Omega(\log n)</tex>
|<tex>\Omega(\log(n))</tex>
+
|-align="center" bgcolor=#FFFFFF
|-
+
|<tex>\mathrm{decreaseKey}</tex>||<tex>\Theta(\log n)</tex>
|decreaseKey
+
|-align="center" bgcolor=#FFFFFF
|<tex>\Theta(\log(n))</tex>
+
|<tex>\mathrm{delete}</tex>||<tex>\Theta(\log n)</tex>
|-
+
|}
|delete
+
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов.
|<tex>\Theta(\log(n))</tex>
 
|}
 
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>head = null</tex>, то есть пирамида не содержит элементов.
 
  
 
=== getMinimum ===
 
=== getMinimum ===
 
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).
 
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).
  
Асимптотика этой операции получается из того, что корней в этом списке не более <tex>\lfloor \log(n) \rfloor + 1</tex>.
+
Так как корней в этом списке не более <tex>\lfloor \log n \rfloor + 1</tex>, то операция выполняется за <tex>O(\log n)</tex>.
 +
 
 +
При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключом <tex>1</tex>.
  
При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем <tex>1</tex>.
+
[[Файл:binHeapExample1_1.png|370px]]
  
[[Файл:binHeapExample1.png|300px]]
+
При использовании указателя на биномиальное дерево, которое содержит минимальный элемент, время для этой операции может быть сведено к <tex>O(1)</tex>. Указатель должен обновляться при выполнении любой операции, кроме <tex>\mathrm{getMinimum}</tex>. Это может быть сделано за <tex>O(\log n)</tex>, не ухудшая время работы других операций.
  
 
=== merge ===
 
=== merge ===
 
Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
 
Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
  
Для этого нам надо сначала слить списки корней <tex>H_1, H_2</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. Для каждого элемента списка известна ссылка на следующего и предыдущего корня. Свойство пирамиды обеспечивает нам в новом списке наличие не более двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. Рассмотрим подробнее процесс прохождения по этому списку:
+
Вот в чем состоит ее суть: пусть есть две биномиальные кучи с <tex>H</tex> и <tex>H'</tex>. Размеры деревьев в кучах соответствуют двоичным числам <tex>m</tex> и <tex>n</tex>, то есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев <tex>B_{k-1}</tex> в дерево    <tex>B_{k}</tex>. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, и считать его верхним (пример работы для одного случая приведен на рисунке справа; в другом случае подвешиваем наоборот).
  
Если текущий корень имеет разные степени с следующим за ним, то ничего с ним не делаем и продолжаем цикл. Это дерево в итоге останется в таком виде в конечной куче(случай <tex>a</tex> на рисунке). Если же степень текущего элемента равна степеням последующих двух вершин(это может случится в том случае, если в каждом из двух исходных деревьев был корень с этой степенью и еще одно дерево образовалось в ходе текущего слияния деревьев; причем более, чем трех корней с одинаковой степенью быть не может по нашему алгоритму и начальным условиям), то оставим это дерево нетронутым, но после на следующем шаге сольем два других дерева с этой степенью. Иными словами переходим к следующей вершине, в которой уже будет происходить слияние(случай <tex>b</tex> на рисунке). В последнем случае мы имеем лишь две подряд вершины с одинаковой степенью корней. В этой ситуаций мы дерево с большим значением в корне вершины подвешиваем к дерево с меньшим значением в корне (случаи <tex> c, d</tex> на рисунке).
+
[[Файл:helpBinaryHeapBoris.png|Пример слияние двух деревьев одного порядка]]
  
Прим. на рисунке <tex>sibling[next-x]</tex> {{---}} следующий элемент в списке для <tex>next-x</tex>
+
Работа этой процедуры начинается с соединения корневых списков куч в единый список, в котором корневые вершины идут в порядке неубывания их степеней.
  
 +
В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за <tex>\Omega(\log n)</tex>.
  
  
[[Файл:binHeapExample2_1.png|300]]
 
  
Пример пирамиды до merge и после:
+
<code>
 
+
'''BinomialHeap''' merge(H1 : '''BinomialHeap''', H2 : '''BinomialHeap'''):
[[Файл:Example5.jpg]]
+
    '''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 ===
 
=== insert ===
Необходимо просто создать биномиальную пирамиду <tex>H'</tex> с одним узлом за время <tex>O(1)</tex> и объединяет ее с биномиальной пирамидой <tex>Н</tex>, содержащей <tex>n</tex> узлов, за время <tex>O(\log(n))</tex>.
+
Чтобы добавить новый элемент в биномиальную кучу нужно создать биномиальную кучу <tex>H'</tex> с единственным узлом, содержащим этот элемент, за время <tex>O(1)</tex> и объединить ее с биномиальной кучей <tex>H</tex> за <tex>O(\log n)</tex>, так как в данном случае куча <tex>H'</tex> содержит лишь одно дерево.
  
 
=== extractMin ===
 
=== extractMin ===
  
Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел. Процедура выполняется за время <tex>O(\log n)</tex>, поскольку всего в списке <tex>O(\log n)</tex> корней биномиальных деревьев. И всего у найденного дерева <tex> k </tex> порядка(с минимальным значением ключа) ровно <tex> k </tex> детей, то сложность перебора этих детей будет тоже <tex>O(\log n)</tex>. То общая асимптотика <tex>O(\log n) + O(\log n) = O(\log n)</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 извлечения минимума]]
  
 
<code>
 
<code>
  Node extractMin(H) {
+
'''Node''' extractMin(H : '''BinomialHeap'''): <font color = "green">//поиск корня х с минимальным значением ключа в списке корней Н: </font>
    //поиск корня х с минимальным значением ключа в списке корней Н
+
    min = <tex>\infty</tex>
    min = <tex>\infty</tex>;
+
    x = ''null''
    x = null;
+
    xBefore = ''null''
    curx = head[H];
+
    curx = H.head
    while curx <tex>\ne</tex> null {
+
    curxBefore = ''null''
      if curx.key < min {
+
    '''while''' curx != ''null''
        min = curx.key;
+
        '''if''' curx.key < min     <font color = "green"> // релаксируем текущий минимум </font>
        x = curx
+
            min = curx.key
      }
+
            x = curx  
      curx = curx.next;
+
            xBefore = curxBefore
    }
+
        curxBefore = curx
     //удаление найденного корня x из списка корней деревьев кучи
+
        curx = curx.sibling
    x.prev.next = x.next;
+
     '''if''' xBefore == ''null''          <font color = "green"> //удаление найденного корня x из списка корней деревьев кучи</font>
     x.next.prev = x.prev;
+
        H.head = x.sibling
   
+
     '''else'''
     //добавление детей элемента x в кучу.
+
        xBefore.sibling = x.sibling
     H' = null; 
+
     H' = ''null''                    <font color = "green">//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на ''null'':</font>
    curx = x.child;
+
    curx = x.child
     while curx <tex>\ne</tex> null {
+
     H'.head = x.child
      p[curx] = null; // удаление элемента x из предков curx
+
     '''while''' curx != ''null''
      head[H'] = curx;
+
        p[curx] = ''null''          <font color = "green">// меняем указатель на родителя узла curx </font>
      H = merge(H, H'); // слияние нашего дерева с текущим деревом H'
+
        curx = curx.sibling      <font color = "green">// переход к следующему ребенку </font>
      curx = curx.sibling;
+
    H = merge(H, H')             <font color = "green">// слияние нашего дерева с деревом H' </font>
    }
+
     '''return''' x
     return x;
 
  }
 
 
 
 
</code>
 
</code>
 
Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи.
 
Все действия выполняются за время <tex>O(\log n)</tex>, так что общее время работы процедуры есть <tex>O(\log n)</tex>.
 
  
 
=== decreaseKey ===
 
=== decreaseKey ===
Следующая процедура уменьшает ключ элемента <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время <tex>O(\log n)</tex>, поскольку глубина вершины <tex>x</tex> есть <tex>O(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
+
Следующая процедура уменьшает ключ элемента <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» как в обычной куче. Процедура выполняется за время <tex>\Theta(\log n)</tex>, поскольку глубина вершины <tex>x</tex> в худшем случае есть <tex>\Theta(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
  
 
<code>
 
<code>
  void decreaseKey(H, x, k) {
+
'''function''' decreaseKey(H : '''BinomialHeap''', x : '''Node''', k : '''int'''):
  if k > key[x] then
+
    '''if''' k > key[x]                     <font color = "green">// проверка на то, что текущий ключ x не меньше передаваемого ключа k </font>
      return;
+
        '''return'''
    key[x] = k;
+
    key[x] = k
    y = x;
+
    y = x
    z = p[y];
+
    z = p[y]
    //поднимаем текущий элемент x с новым ключом k, пока
+
    '''while''' z != ''null'' '''and''' key[y] < key[z] <font color = "green">// поднимаем x с новым ключом k, пока это значение меньше значения в родительской вершине </font>
    //это значение меньше значения в родительской вершине  
+
        swap(key[y], key[z])
    while z <tex>\ne</tex> null and key[y] < key[z] do {
+
        y = z
      swap(key[y], key[z]);
+
        z = p[y]
      y = z;
 
      z = p[y];
 
    }
 
  }
 
 
</code>
 
</code>
  
 
Пример работы процедуры проиллюстрирован на рисунке (<tex>y</tex> {{---}} уменьшаемый элемент, <tex>z</tex> {{---}} его предок).
 
Пример работы процедуры проиллюстрирован на рисунке (<tex>y</tex> {{---}} уменьшаемый элемент, <tex>z</tex> {{---}} его предок).
  
[[Файл:binHeapExample3.png|400px]]
+
[[Файл:binHeapExample3_2.png|370px]]
  
 
=== delete ===
 
=== delete ===
Удаление ключа сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения, а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>O(\log n)</tex>.
+
Удаление ключа сводится к операциям <math>\mathrm {decreaseKey}</math> и <math>\mathrm {extractMin}</math>: сначала нужно уменьшить ключ до минимально возможного значения, а затем извлечь вершину с минимальным ключом. В процессе выполнения процедуры этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>\Theta(\log n)</tex>, поскольку каждая из операций, которые используется в реализации, работают за <tex>\Theta(\log n)</tex>.
  
 
<code>
 
<code>
   void delete(H, x) {
+
   '''function''' delete(H : '''BinomialHeap''', x : '''Node'''):
    //уменшение ключа до минимально вохможного значения
+
     decreaseKey(H, x, <tex>-\infty</tex>) <font color = "green">// уменьшение ключа до минимально возможного значения </font>
     decreaseKey(H, x, <tex>-\infty</tex>);
+
     extractMin(H)          <font color = "green">// удаление "всплывшего" элемента </font>
     //удаление "всплывшего" элемента
 
    extractMin(H);
 
  }
 
 
</code>
 
</code>
  
= Источники =
+
=== Персистентность ===
* [http://www.intuit.ru/department/algorithms/dscm/7/ Биномиальные кучи  — INTUIT.ru]
+
Биноминальную кучу можно сделать [[Персистентные структуры данных|персистентной]] при реализации на односвязных списках<ref>[https://github.com/kgeorgiy/okasaki/tree/master/Okasaki/Chapter3 Github {{---}} реализация на Haskell]</ref>.  Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя. Односвязанные списки хороши с точки зрения функционального программирования, так как голова списка не будет достижима из потомков. Тогда при добавлениии новой версии в голову или удалении объявляя другую вершину новой головой мы не будем терять старые версии, которые останутся на месте, так как фактически односвязный список с операциями на голове это [[Персистентный стек|персистентный стек]], который является полностью персистентной функциональной структурой. При этом каждая версия будет поддерживать возможность изменения, что является полным уровнем персистентности. Также поддерживается операция <tex>\mathrm {merge}</tex> для всех версий биномиальных куч, что позволяет получать новую версию путём сливания старых. Это добавляет конфлюэнтный уровень персистентности.
* [http://en.wikipedia.org/wiki/Binomial_heap Binomial heap — Wikipedia]
+
 
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538-558. — ISBN 5-8489-0857-4
+
== См. также ==
 +
* [[Двоичная куча]]
 +
* [[Фибоначчиева куча]]
 +
* [[Левосторонняя куча]]
 +
* [[Куча Бродала-Окасаки]]
 +
 
 +
==Примечания==
 +
 
 +
<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
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Приоритетные очереди]]
 +
[[Категория: Структуры данных‏‎]]

Текущая версия на 19:22, 4 сентября 2022

Пример биномиальных деревьев [math]B_0, B_2, B_3[/math]

Биномиальное дерево

Определение:
Биномиальное дерево [math]B_k[/math] (англ. binomial tree) — дерево, определяемое для каждого [math]k = 0, 1, 2, \dots [/math] следующим образом: [math]B_0[/math] — дерево, состоящее из одного узла; [math]B_k[/math] состоит из двух биномиальных деревьев [math]B_{k-1}[/math], связанных вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.


Свойства биномиальных деревьев

Утверждение:
Биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами имеет [math]2^k[/math] узлов.
[math]\triangleright[/math]

Докажем по индукции:

База [math]k = 1[/math] — верно. Пусть для некоторого [math]k [/math] условие верно, то докажем, что для [math]k + 1[/math] это также верно:

Так как в дереве порядка [math]k+1[/math] вдвое больше узлов, чем в дереве порядка [math]k[/math], то дерево порядка [math]k+1[/math] имеет [math]2^k \cdot 2 = 2^{k+1}[/math] узлов. Переход доказан, то биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами имеет [math]2^k[/math] узлов.
[math]\triangleleft[/math]
Утверждение:
Биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами имеет высоту [math]k[/math].
[math]\triangleright[/math]

Докажем по индукции:

База [math]k = 1[/math] — верно. Пусть для некоторого [math]k [/math] условие верно, то докажем, что для [math]k + 1[/math] это также верно:

Так как в дереве порядка [math]k+1[/math] высота больше на [math]1[/math] (так как мы подвешиваем к текущему дереву дерево того же порядка), чем в дереве порядка [math]k[/math], то дерево порядка [math]k+1[/math] имеет высоту [math]k + 1[/math]. Переход доказан, то биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами имеет высоту [math]k[/math].
[math]\triangleleft[/math]
Утверждение:
Биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами имеет ровно [math] k\choose i[/math] узлов на высоте [math]i[/math].
[math]\triangleright[/math]

Докажем по индукции:

База [math]k = 1[/math] — верно. Пусть для некоторого [math]k [/math] условие верно, то докажем, что для [math]k + 1[/math] это также верно:

Рассмотрим [math]i[/math] уровень дерева [math]B_{k+1}[/math]. Дерево [math]B_{k+1}[/math] было получено подвешиванием одного дерева порядка [math]k[/math] к другому. Тогда на [math]i[/math] уровне дерева [math]B_{k+1}[/math] всего узлов [math] {k\choose i} [/math] [math]+[/math] [math]{k\choose {i - 1}}[/math], так как от подвешенного дерева в дерево порядка [math]k+1[/math] нам пришли узлы глубины [math]i-1[/math]. То для [math]i[/math]-го уровня дерева [math]B_{k+1}[/math] количество узлов [math] {k\choose i}[/math] [math]+[/math] [math]{k\choose {i - 1}}[/math] [math]=[/math] [math]{{k + 1}\choose i} [/math]. Переход доказан, то биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами имеет ровно [math] {k\choose i}[/math] узлов на высоте [math]i[/math].
[math]\triangleleft[/math]
Утверждение:
Биномиальное дерево [math]B_k[/math] с [math]n[/math] вершинами имеет корень степени [math]k[/math]; степень всех остальных вершин меньше степени корня биномиального дерева;
[math]\triangleright[/math]
Так как в дереве порядка [math]k+1[/math] степень корня больше на [math]1[/math], чем в дереве порядка [math]k[/math], а в дереве нулевого порядка степень корня [math]0[/math], то дерево порядка [math]k[/math] имеет корень степени [math]k[/math]. И так как при таком увеличении порядка (при переходе от дерева порядка [math]k[/math] к [math]k+1[/math]) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться.
[math]\triangleleft[/math]
Утверждение:
В биномиальном дереве [math]B_k[/math] с [math]n[/math] вершинами максимальная степень произвольного узла равна [math]\log n[/math].
[math]\triangleright[/math]
Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Так как степень корня дерева порядка [math]k[/math] равна [math]k[/math], а узлов в этом дереве [math]n = 2^k[/math], то прологарифмировав обе части получаем, что [math]k=O(\log n)[/math], то степень произвольного узла не более [math]\log n[/math].
[math]\triangleleft[/math]

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

Определение:
Биномиальная куча (англ. binomial heap) представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:
  • каждое биномиальное дерево в куче подчиняется свойству неубывающей кучи: ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей кучи дерево),
  • для любого неотрицательного целого [math]k[/math] найдется не более одного биномиального дерева, чей корень имеет степень [math]k[/math].


Представление биномиальных куч

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

  • [math]key[/math] — ключ (вес) элемента,
  • [math]parent[/math] — указатель на родителя узла,
  • [math]child[/math] — указатель на левого ребенка узла,
  • [math]sibling[/math] — указатель на правого брата узла,
  • [math]degree[/math] — степень узла (количество дочерних узлов данного узла).

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

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

Рассмотрим операции, которые можно производить с биномиальной кучей. Время работы указано в таблице:

Операция Время работы
[math]\mathrm{insert}[/math] [math]O(\log n)[/math]
[math]\mathrm{getMinimum}[/math] [math]O(\log n)[/math]
[math]\mathrm{extractMin}[/math] [math]\Theta(\log n)[/math]
[math]\mathrm{merge}[/math] [math]\Omega(\log n)[/math]
[math]\mathrm{decreaseKey}[/math] [math]\Theta(\log n)[/math]
[math]\mathrm{delete}[/math] [math]\Theta(\log n)[/math]

Обозначим нашу кучу за [math]H[/math]. То пусть [math]H.head[/math] — указатель на корень биномиального дерева минимального порядка этой кучи. Изначально [math]H.head = null[/math], то есть куча не содержит элементов.

getMinimum

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

Так как корней в этом списке не более [math]\lfloor \log n \rfloor + 1[/math], то операция выполняется за [math]O(\log n)[/math].

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

BinHeapExample1 1.png

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

merge

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

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

Пример слияние двух деревьев одного порядка

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

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


BinomialHeap merge(H1 : BinomialHeap, H2 : BinomialHeap):
   if H1 == null 
       return H2 
   if H2 == null 
       return H1  
   H.head = null                     // H — результат слияния 
   curH = H.head                     // слияние корневых списков 
   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                     // объединение деревьев одной степени 
   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

insert

Чтобы добавить новый элемент в биномиальную кучу нужно создать биномиальную кучу [math]H'[/math] с единственным узлом, содержащим этот элемент, за время [math]O(1)[/math] и объединить ее с биномиальной кучей [math]H[/math] за [math]O(\log n)[/math], так как в данном случае куча [math]H'[/math] содержит лишь одно дерево.

extractMin

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

Рассмотрим пошагово алгоритм:

  • Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево [math]B_k[/math]. Время работы этого шага алгоритма [math]\Theta(\log n)[/math].
  • Удаляем дерево [math]B_k[/math] из кучи [math]H[/math]. Иными словами, удаляем его корень из списка корней кучи. Это можно сделать за время [math]O(1)[/math].
  • Пусть [math]H'[/math] — куча детей найденного корня. При этом мы для каждого из ребенка устанавливаем указатель на предка равным [math]null[/math]. После этого сливаем кучу [math]H'[/math] c [math]H[/math] за [math]\Omega(\log n)[/math].

Процедура выполняется за время [math]\Theta(\log n)[/math], поскольку всего в списке [math]\Theta(\log n)[/math] корней биномиальных деревьев. И всего у найденного дерева [math] k [/math] порядка (с минимальным значением ключа) ровно [math] k [/math] детей, то сложность перебора этих детей будет тоже [math]\Theta(\log n)[/math]. А процесс слияния выполняется за [math]\Omega(\log n)[/math]. Таким образом, операция выполняется [math]\Theta(\log n)[/math].

Примеp извлечения минимума

Node extractMin(H : BinomialHeap): //поиск корня х с минимальным значением ключа в списке корней Н: 
    min = [math]\infty[/math]
    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
   if xBefore == null           //удаление найденного корня x из списка корней деревьев кучи
       H.head = x.sibling
   else 
       xBefore.sibling = x.sibling 
   H' = null                    //построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на null:
   curx = x.child
   H'.head = x.child
   while curx != null 
       p[curx] = null           // меняем указатель на родителя узла curx 
       curx = curx.sibling      // переход к следующему ребенку 
   H = merge(H, H')             // слияние нашего дерева с деревом H' 
   return x

decreaseKey

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

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

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

BinHeapExample3 2.png

delete

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

 function delete(H : BinomialHeap, x : Node): 
   decreaseKey(H, x, [math]-\infty[/math]) // уменьшение ключа до минимально возможного значения 
   extractMin(H)           // удаление "всплывшего" элемента 

Персистентность

Биноминальную кучу можно сделать персистентной при реализации на односвязных списках[1]. Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя. Односвязанные списки хороши с точки зрения функционального программирования, так как голова списка не будет достижима из потомков. Тогда при добавлениии новой версии в голову или удалении объявляя другую вершину новой головой мы не будем терять старые версии, которые останутся на месте, так как фактически односвязный список с операциями на голове это персистентный стек, который является полностью персистентной функциональной структурой. При этом каждая версия будет поддерживать возможность изменения, что является полным уровнем персистентности. Также поддерживается операция [math]\mathrm {merge}[/math] для всех версий биномиальных куч, что позволяет получать новую версию путём сливания старых. Это добавляет конфлюэнтный уровень персистентности.

См. также

Примечания

Источники информации