Редактирование: Биномиальная куча

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Биномиальное дерево <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>, связанных вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.
+
'''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{---}} дерево, состоящее из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.
 
}}
 
}}
  
Строка 12: Строка 12:
  
 
{{Утверждение
 
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет <tex>2^k</tex> узлов.
+
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет <tex>2^k</tex> узлов
 
|proof=
 
|proof=
 
Докажем по индукции:
 
Докажем по индукции:
Строка 22: Строка 22:
  
 
{{Утверждение
 
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет высоту <tex>k</tex>.
+
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет высоту <tex>k</tex>;
 
|proof=
 
|proof=
 
Докажем по индукции:
 
Докажем по индукции:
Строка 33: Строка 33:
  
 
{{Утверждение
 
{{Утверждение
|statement=Биномиальное дерево <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 dpi = "165"> k\choose i</tex> узлов на высоте <tex>i</tex>;
 
|proof=
 
|proof=
 
Докажем по индукции:
 
Докажем по индукции:
Строка 39: Строка 39:
 
База <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 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>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 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 dpi = "165">{k\choose {i - 1}}</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>.
 
}}
 
}}
  
Строка 57: Строка 57:
 
{{Определение
 
{{Определение
 
|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> {{---}} степень узла (количество дочерних узлов данного узла).
  
Строка 75: Строка 75:
  
 
Рассмотрим операции, которые можно производить с биномиальной кучей. Время работы указано в таблице:
 
Рассмотрим операции, которые можно производить с биномиальной кучей. Время работы указано в таблице:
{| class="wikitable" style="width:10cm" border=1
+
{| border="1"
|+
+
|<math>\mathrm {insert}</math>
|-align="center" bgcolor=#EEEEFF
+
|<tex>O(\log n)</tex>
! Операция || Время работы
+
|-
|-align="center" bgcolor=#FFFFFF
+
|<math>\mathrm {getMinimum}</math>
|<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>
+
|<math>\mathrm {extractMin}</math>
|-align="center" bgcolor=#FFFFFF
+
|<tex>\Theta(\log n)</tex>
||<tex>\mathrm{extractMin}</tex>||<tex>\Theta(\log n)</tex>
+
|-
|-align="center" bgcolor=#FFFFFF
+
|<math>\mathrm {merge}</math>
|<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>
+
|<math>\mathrm {decreaseKey}</math>
|-align="center" bgcolor=#FFFFFF
+
|<tex>\Theta(\log n)</tex>
|<tex>\mathrm{delete}</tex>||<tex>\Theta(\log n)</tex>
+
|-
|}
+
|<math>\mathrm {delete}</math>
 +
|<tex>\Theta(\log n)</tex>
 +
|}
 
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов.
 
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов.
  
Строка 102: Строка 104:
  
 
[[Файл:binHeapExample1_1.png|370px]]
 
[[Файл:binHeapExample1_1.png|370px]]
 
При использовании указателя на биномиальное дерево, которое содержит минимальный элемент, время для этой операции может быть сведено к <tex>O(1)</tex>. Указатель должен обновляться при выполнении любой операции, кроме <tex>\mathrm{getMinimum}</tex>. Это может быть сделано за <tex>O(\log n)</tex>, не ухудшая время работы других операций.
 
  
 
=== merge ===
 
=== merge ===
Строка 119: Строка 119:
  
 
<code>
 
<code>
  '''BinomialHeap''' merge(H1 : '''BinomialHeap''', H2 : '''BinomialHeap'''):
+
  '''Node''' merge('''binomialHeap''' H1, H2)
     '''if''' H1 == ''null''
+
     '''if''' H1 == null  
 
         '''return''' H2  
 
         '''return''' H2  
     '''if''' H2 == ''null''
+
     '''if''' H2 == null  
 
         '''return''' H1   
 
         '''return''' H1   
     H.head = ''null''                   <font color = "green"> // H {{---}} результат слияния </font>
+
     H.head = null                    <font color = "green"> // H - результат слияния </font>
 
     curH = H.head                    <font color = "green"> // слияние корневых списков </font>
 
     curH = H.head                    <font color = "green"> // слияние корневых списков </font>
 
     curH1 = H1.head
 
     curH1 = H1.head
 
     curH2 = H2.head
 
     curH2 = H2.head
     '''while''' curH1 != ''null'' '''and''' curH2 != ''null''
+
     '''while''' curH1 != null '''and''' curH2 != null  
 
         '''if''' curH1.degree < curH2.degree  
 
         '''if''' curH1.degree < curH2.degree  
 
             curH.sibling = curH1
 
             curH.sibling = curH1
Строка 137: Строка 137:
 
             curH = curH2
 
             curH = curH2
 
             curH2 = curH2.sibling
 
             curH2 = curH2.sibling
     '''if''' curH1 == ''null''
+
     '''if''' curH1 == null  
         '''while''' curH2 != ''null''
+
         '''while''' curH2 != null  
 
             curH.sibling = curH2
 
             curH.sibling = curH2
 
             curH2 = curH2.sibling
 
             curH2 = curH2.sibling
 
     '''else'''  
 
     '''else'''  
         '''while''' curH1 != ''null''
+
         '''while''' curH1 != null  
 
             curH.sibling = curH1
 
             curH.sibling = curH1
 
             curH1 = curH1.sibling
 
             curH1 = curH1.sibling
 
     curH = H.head                    <font color = "green"> // объединение деревьев одной степени </font>
 
     curH = H.head                    <font color = "green"> // объединение деревьев одной степени </font>
     '''while''' curH.sibling != ''null''
+
     '''while''' curH.sibling != null  
 
         '''if''' curH.degree == curH.sibling.degree
 
         '''if''' curH.degree == curH.sibling.degree
 
             p[curH] = curH.sibling
 
             p[curH] = curH.sibling
Строка 166: Строка 166:
 
Рассмотрим пошагово алгоритм:
 
Рассмотрим пошагово алгоритм:
 
* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <tex>B_k</tex>. Время работы этого шага алгоритма <tex>\Theta(\log n)</tex>.
 
* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <tex>B_k</tex>. Время работы этого шага алгоритма <tex>\Theta(\log n)</tex>.
* Удаляем дерево <tex>B_k</tex> из кучи <tex>H</tex>. Иными словами, удаляем его корень из списка корней кучи. Это можно сделать за время <tex>O(1)</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>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>.
+
Процедура выполняется за время <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 извлечения минимума]]
 
[[Файл:BinHeapExampleNew31.png|700px|Примеp извлечения минимума]]
  
 
<code>
 
<code>
  '''Node''' extractMin(H : '''BinomialHeap'''): <font color = "green">//поиск корня х с минимальным значением ключа в списке корней Н: </font>
+
  '''Node''' extractMin('''binomialHeap''' H) <font color = "green">//поиск корня х с минимальным значением ключа в списке корней Н: </font>
 
     min = <tex>\infty</tex>
 
     min = <tex>\infty</tex>
     x = ''null''
+
     x = null
     xBefore = ''null''
+
     xBefore = null
 
     curx = H.head
 
     curx = H.head
     curxBefore = ''null''
+
     curxBefore = null
     '''while''' curx != ''null''
+
     '''while''' curx != null  
 
         '''if''' curx.key < min      <font color = "green"> // релаксируем текущий минимум </font>
 
         '''if''' curx.key < min      <font color = "green"> // релаксируем текущий минимум </font>
 
             min = curx.key
 
             min = curx.key
Строка 187: Строка 187:
 
         curxBefore = curx
 
         curxBefore = curx
 
         curx = curx.sibling
 
         curx = curx.sibling
     '''if''' xBefore == ''null''         <font color = "green"> //удаление найденного корня x из списка корней деревьев кучи</font>
+
     '''if''' xBefore == null          <font color = "green"> //удаление найденного корня x из списка корней деревьев кучи</font>
 
         H.head = x.sibling
 
         H.head = x.sibling
 
     '''else'''  
 
     '''else'''  
 
         xBefore.sibling = x.sibling  
 
         xBefore.sibling = x.sibling  
     H' = ''null''                   <font color = "green">//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на ''null'':</font>
+
     H' = null                    <font color = "green">//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на null:</font>
 
     curx = x.child
 
     curx = x.child
 
     H'.head = x.child
 
     H'.head = x.child
     '''while''' curx != ''null''
+
     '''while''' curx != null  
         p[curx] = ''null''           <font color = "green">// меняем указатель на родителя узла curx </font>
+
         p[curx] = null          <font color = "green">// меняем указатель на родителя узла curx </font>
 
         curx = curx.sibling      <font color = "green">// переход к следующему ребенку </font>
 
         curx = curx.sibling      <font color = "green">// переход к следующему ребенку </font>
 
     H = merge(H, H')            <font color = "green">// слияние нашего дерева с деревом H' </font>
 
     H = merge(H, H')            <font color = "green">// слияние нашего дерева с деревом H' </font>
Строка 205: Строка 205:
  
 
<code>
 
<code>
  '''function''' decreaseKey(H : '''BinomialHeap''', x : '''Node''', k : '''int'''):
+
  '''function''' decreaseKey('''binomialHeap''' H, '''node''' x, '''int''' k)
 
     '''if''' k > key[x]                      <font color = "green">// проверка на то, что текущий ключ x не меньше передаваемого ключа k </font>  
 
     '''if''' k > key[x]                      <font color = "green">// проверка на то, что текущий ключ x не меньше передаваемого ключа k </font>  
 
         '''return'''
 
         '''return'''
Строка 211: Строка 211:
 
     y = x
 
     y = x
 
     z = p[y]
 
     z = p[y]
     '''while''' z != ''null'' '''and''' key[y] < key[z] <font color = "green">// поднимаем  x с новым ключом k, пока это значение меньше значения в родительской вершине </font>
+
     '''while''' z != null '''and''' key[y] < key[z] <font color = "green">// поднимаем  x с новым ключом k, пока это значение меньше значения в родительской вершине </font>
 
         swap(key[y], key[z])
 
         swap(key[y], key[z])
 
         y = z
 
         y = z
Строка 225: Строка 225:
  
 
<code>
 
<code>
   '''function''' delete(H : '''BinomialHeap''', x : '''Node'''):
+
   '''function''' delete('''binomialHeap''' H, '''node''' x)  
 
     decreaseKey(H, x, <tex>-\infty</tex>) <font color = "green">// уменьшение ключа до минимально возможного значения </font>
 
     decreaseKey(H, x, <tex>-\infty</tex>) <font color = "green">// уменьшение ключа до минимально возможного значения </font>
 
     extractMin(H)          <font color = "green">// удаление "всплывшего" элемента </font>
 
     extractMin(H)          <font color = "green">// удаление "всплывшего" элемента </font>
 
</code>
 
</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://www.intuit.ru/department/algorithms/dscm/7/ Биномиальные кучи  — INTUIT.ru]
* [http://en.wikipedia.org/wiki/Binomial_heap Wikipedia {{---}} Binomial heap]
+
* [http://en.wikipedia.org/wiki/Binomial_heap Binomial heap — Wikipedia]
* [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
 
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 538—558. — ISBN 5-8489-0857-4
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных‏‎]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)