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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 6 участников)
Строка 1: Строка 1:
'''''Тонкая куча''''' {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
+
'''Тонкая куча''' (англ. ''Thin heap'') {{---}} структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
  
 
Тонкие кучи, как и многие другие [[Двоичная куча|кучеобразные]] структуры, аналогичны [[Биномиальная куча|биномиальным кучам]].
 
Тонкие кучи, как и многие другие [[Двоичная куча|кучеобразные]] структуры, аналогичны [[Биномиальная куча|биномиальным кучам]].
Строка 6: Строка 6:
 
{{Определение
 
{{Определение
 
|id=thin_tree_def
 
|id=thin_tree_def
|definition='''Тонкое дерево''' (''thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов.
+
|definition='''Тонкое дерево''' (англ. ''Thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов.
 
}}
 
}}
  
Строка 17: Строка 17:
  
 
Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим:
 
Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим:
* <tex>Degree(x)</tex> {{---}} количество детей узла <tex>x</tex>.
+
* <tex>\mathtt{Degree(x)}</tex> {{---}} количество детей узла <tex>x</tex>.
* <tex>Rank(x)</tex> {{---}} ранг соответствующего узла в [[Биномиальная куча#Биномиальное дерево|биномиальном дереве]] <tex>B_k</tex>.
+
* <tex>\mathtt{Rank(x)}</tex> {{---}} ранг соответствующего узла в [[Биномиальная куча#Биномиальное дерево|биномиальном дереве]] <tex>B_k</tex>.
  
 
== Свойства тонкого дерева ==
 
== Свойства тонкого дерева ==
Строка 24: Строка 24:
 
|id=about_thin_tree
 
|id=about_thin_tree
 
|statement=Тонкое дерево обладает следующими свойствами:
 
|statement=Тонкое дерево обладает следующими свойствами:
# Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полон); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (не полон).
+
# Для любого узла <tex>x</tex> либо <tex>\mathtt{Degree(x)=Rank(x)}</tex>, в этом случае говорим, что узел <tex>x</tex> не тонкий (полон); либо <tex>\mathtt{Degree(x)=Rank(x)-1}</tex>, в этом случае говорим, что узел <tex>x</tex> тонкий (не полон).
# Корень не помечен (полон).
+
# Корень не тонкий (полон).
# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
+
# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>\mathtt{0,1,2,...,Degree(x)-1}</tex>.
# Узел <tex>x</tex> помечен тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
+
# Узел <tex>x</tex> тонкий тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
 
}}
 
}}
  
[[Файл:Thin_tree_examples.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются помеченными (не имеют самого левого сына)]]
+
[[Файл:Thin_trees.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются тонкими (не имеют самого левого сына)]]
 
<br clear="all" />
 
<br clear="all" />
  
= Тонкая куча =
+
== Тонкая куча ==
  
 
{{Определение
 
{{Определение
 
|id=thin_forest_def
 
|id=thin_forest_def
|definition='''Тонкий лес''' (''thin forest'') {{---}} это набор тонких деревьев, ранги которых не обязательно попарно различны.
+
|definition='''Тонкий лес''' (англ. ''Thin forest'') {{---}} это набор тонких деревьев, ранги которых не обязательно попарно различны.
 
}}
 
}}
  
Строка 48: Строка 48:
 
{{Определение
 
{{Определение
 
|id=thin_heap_def
 
|id=thin_heap_def
|definition='''Тонкая куча''' (''thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям [[Двоичная куча|кучи]].
+
|definition='''Тонкая куча''' (англ. ''Thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям [[Двоичная куча|кучи]].
 
}}
 
}}
  
Строка 56: Строка 56:
 
|id=max_rank_th
 
|id=max_rank_th
 
|about=О максимальном ранге узла
 
|about=О максимальном ранге узла
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phi=\frac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
+
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex>\varphi=\dfrac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \Phi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи.
+
|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \varphi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи.
  
 
Действительно, пусть <tex>T_k</tex> {{---}} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>k</tex>. По свойствам <tex>1</tex> и <tex>3</tex> тонкого дерева получаем следующие соотношения:
 
Действительно, пусть <tex>T_k</tex> {{---}} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>k</tex>. По свойствам <tex>1</tex> и <tex>3</tex> тонкого дерева получаем следующие соотношения:
  
<tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_i</tex> для <tex>k \geqslant 2</tex>
+
<tex>T_0=1,T_1=1,T_k \geqslant 1+\sum\limits_{i=0}^{k-2}T_i</tex> для <tex>k \geqslant 2</tex>
  
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \Phi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
+
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \varphi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
  
Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> тонкого дерева в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>.  
+
Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> тонкого дерева в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\varphi}(n)+1</tex>.  
  
Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n)-1}</tex>.
+
Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \varphi^{D(n)-1}</tex>.
  
Отсюда следует, что <tex>D(n)\leqslant\log_{\Phi}(n)+1</tex>.
+
Отсюда следует, что <tex>D(n)\leqslant\log_{\varphi}(n)+1</tex>.
 
}}
 
}}
  
== Представление тонкой кучи ==
+
== Структура ==
 +
=== Структура узла ===
 +
'''struct''' Node
 +
    '''int''' key <span style="color:#008000">    // ключ</span>
 +
    '''int''' rank <span style="color:#008000">    // ранг узла</span>
 +
    '''Node''' child <span style="color:#008000">  // указатель на самого левого ребенка узла</span>
 +
    '''Node''' right <span style="color:#008000">  // указатель на правого брата узла, либо на следующий корень, если текущий узел корень</span>
 +
    '''Node''' left <span style="color:#008000">  // указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень</span>
  
Тонкую кучу можно представить как [[Список#Односвязный список|односвязный список]] корней тонких деревьев, причем корень с минимальным ключом должен быть первым в списке.
+
Для ускорения проверки на тонкость (англ. ''thinness'') можно отдельно хранить тонкость вершины.
 
 
Поскольку при работе с тонкой кучей ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины.
 
 
 
Таким образом, для эффективной работы тонкой кучи необходимы следующие поля узла:
 
*<tex>key</tex> {{---}} ключ (вес) элемента;
 
*<tex>child</tex> {{---}} указатель на самого левого ребенка узла;
 
*<tex>right</tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
 
*<tex>left</tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень;
 
*<tex>rank</tex> {{---}} ранг узла (количество дочерних узлов данного узла).
 
 
 
Для ускорения проверки на тонкость (''thinness'') можно отдельно хранить помеченность вершины.
 
 
Также в вершине можно хранить любую дополнительную информацию.
 
Также в вершине можно хранить любую дополнительную информацию.
  
Для работы с тонкой кучей достаточно иметь [[Список#Односвязный список|односвязный список]] ее корней.
+
=== Структура кучи ===
 
+
'''struct''' ThinHeap
 +
    '''Node''' first <span style="color:#008000">  // указатель на корень дерева с минимальным ключом</span>
 +
    '''Node''' last <span style="color:#008000">  // указатель на последний корень</span>
 
== Операции над тонкой кучей ==
 
== Операции над тонкой кучей ==
  
 
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
 
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
{| border="1"
+
 
|-align="center"
+
{| class="wikitable" style="width:10cm" border=1
|<tex>makeHeap</tex>
+
|+
|<tex>O(1)</tex>
+
|-align="center" bgcolor=#EEEEFF
|-align="center"
+
! Операция || Время работы
|<tex>insert</tex>
+
|-align="center" bgcolor=#FFFFFF
|<tex>O(1)</tex>
+
|<tex>\mathrm{makeHeap}</tex>||<tex>O(1)</tex>
|-align="center"
+
|-align="center" bgcolor=#FFFFFF
|<tex>getMin</tex>
+
|<tex>\mathrm{insert}</tex>||<tex>O(1)</tex>
|<tex>O(1)</tex>
+
|-align="center" bgcolor=#FFFFFF
|-align="center"
+
||<tex>\mathrm{getMin}</tex>||<tex>O(1)</tex>
|<tex>meld</tex>
+
|-align="center" bgcolor=#FFFFFF
|<tex>O(1)</tex>
+
|<tex>\mathrm{merge}</tex>||<tex>O(1)</tex>
|-align="center"
+
|-align="center" bgcolor=#FFFFFF
|<tex>extractMin</tex>
+
|<tex>\mathrm{extractMin}</tex>||<tex>O(\log(n))</tex>
|<tex>O(\log(n))</tex>
+
|-align="center" bgcolor=#FFFFFF
|-align="center"
+
|<tex>\mathrm{decreaseKey}</tex>||<tex>O(1)</tex>
|<tex>decreaseKey</tex>
+
|-align="center" bgcolor=#FFFFFF
|<tex>O(1)</tex>
+
|<tex>\mathrm{delete}</tex>||<tex>O(\log(n))</tex>
|-align="center"
+
|}
|<tex>delete</tex>
 
|<tex>O(\log(n))</tex>
 
|}
 
  
 
Многие операции над тонкой кучей выполняются так же, как и над [[Фибоначчиева куча|фиббоначиевой]].
 
Многие операции над тонкой кучей выполняются так же, как и над [[Фибоначчиева куча|фиббоначиевой]].
Строка 121: Строка 116:
 
Для [[Амортизационный анализ|амортизационного анализа]] операций применим [[Амортизационный анализ#Метод потенциалов|метод потенциалов]].
 
Для [[Амортизационный анализ|амортизационного анализа]] операций применим [[Амортизационный анализ#Метод потенциалов|метод потенциалов]].
  
Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество тонких деревьев в куче, а <tex>m</tex> {{---}} это количество помеченных вершин.
+
Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество тонких деревьев в куче, а <tex>m</tex> {{---}} это количество тонких вершин.
  
 
{{Утверждение
 
{{Утверждение
Строка 130: Строка 125:
 
}}
 
}}
 
   
 
   
 +
Пусть <tex>\mathtt{Node}</tex> {{---}} узел тонкого дерева, а <tex>\mathtt{ThinHeap}</tex> {{---}} тонкая куча, причём <tex>\mathtt{ThinHeap}</tex> содержит ссылки на первый и последний корень <tex>\mathtt{first}</tex> и <tex>\mathtt{last}</tex> соответственно.
 +
 +
Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>\mathtt{Degree(x) - 1}</tex>.
 +
 +
<code>
 +
'''bool''' isThin(x: '''Node'''):
 +
  '''if''' x.rank == 1
 +
      '''return''' x.child == ''null''
 +
  '''else'''
 +
      '''return''' x.child.rank + 1 != x.rank
 +
</code>
 +
 
=== makeHeap ===
 
=== makeHeap ===
 
Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
 
Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
 +
 +
<code>
 +
'''ThinHeap''' makeHeap():
 +
    H.first = ''null''
 +
    H.last = ''null'' 
 +
    '''return''' H
 +
</code>
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
Строка 137: Строка 151:
 
=== insert ===
 
=== insert ===
  
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла с ключом <tex>x</tex>, добавить его в корневой список на первое место, если этот ключ минимален, иначе на второе. Потенциал <tex>\Phi</tex> увеличивается на 1.
+
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла <tex>x</tex> с ключом <tex>x.key</tex>, добавить его в корневой список на первое место, если этот ключ минимален, либо на последнее. Потенциал <tex>\Phi</tex> увеличивается на 1.
 +
 
 +
<code>
 +
'''void''' insert(H: '''ThinHeap''', x: '''Node'''):
 +
    '''if''' H.first == ''null''
 +
      H.first = x
 +
      H.last = x
 +
    '''else'''
 +
      '''if''' x.key < H.first.key
 +
          x.right = H.first
 +
          H.first = x
 +
      '''else'''
 +
          H.last.right = x
 +
          H.last = x 
 +
</code>
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
Строка 144: Строка 172:
  
 
Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал <tex>\Phi</tex> не меняется.  
 
Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал <tex>\Phi</tex> не меняется.  
 +
 +
<code>
 +
'''Node''' getMin(H: '''ThinHeap'''):
 +
    '''return''' H.first
 +
</code>
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
  
=== meld ===
+
=== merge ===
  
 
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
 
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
 +
 +
<code>
 +
'''ThinHeap''' merge(H1: '''ThinHeap''', H2: '''ThinHeap'''):
 +
    '''if''' H1.first == ''null''
 +
      '''return''' H2
 +
    '''else'''
 +
      '''if''' H2.first == ''null''
 +
          '''return''' H1
 +
      '''else'''
 +
          '''if''' H1.first.key < H2.first.key
 +
            H1.last.right = H2.first
 +
            H1.last = H2.last
 +
            '''return''' H1
 +
          '''else'''
 +
            H2.last.right = H1.first
 +
            H2.last = H1.last
 +
            '''return''' H2
 +
</code>
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
Строка 156: Строка 207:
 
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
 
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
 
# Удалить корень с минимальным ключом из корневого списка.
 
# Удалить корень с минимальным ключом из корневого списка.
# Уменьшить ранг для всех его помеченных детей.
+
# Уменьшить ранг для всех его тонких детей.
 
# Cлить детей с корневым списком.
 
# Cлить детей с корневым списком.
 
# Объединять, пока возможно, тонкие деревья одного ранга.
 
# Объединять, пока возможно, тонкие деревья одного ранга.
Строка 166: Строка 217:
 
При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на <tex>1</tex> больше.
 
При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на <tex>1</tex> больше.
  
Пусть мы сделали <tex>ls</tex> связывающих шагов (''linking steps'') во время добавления в массив.
+
<code>
 +
'''Node''' extractMin(H: '''ThinHeap'''):
 +
    <span style="color:#008000">// Удаляем минимальный корень из корневого списка</span>
 +
    tmp = H.first
 +
    H.first = H.first.right
 +
    '''if''' H.first == ''null''
 +
      H.last = ''null''
 +
    <span style="color:#008000">// Снимаем тонкость с его детей и добавляем их в корневой список</span>
 +
    x = tmp.first.child
 +
    '''while''' x != ''null''
 +
      '''if''' isThin(x)
 +
          x.rank = x.rank - 1
 +
      x.left = ''null''
 +
      next = x.right
 +
      insert(H, x)
 +
      x = next
 +
    <span style="color:#008000">// Объединяем все корни одного ранга с помощью вспомогательного массива aux</span>
 +
    max = -1
 +
    x = H.first
 +
    '''while''' x != ''null''
 +
      '''while''' aux[x.rank] != ''null''
 +
          next = x.right
 +
          '''if''' aux[x.rank].key < x.key
 +
            swap(aux[x.rank], x)
 +
          aux[x.rank].right = x.child
 +
          x.child.left = aux[x.rank]
 +
          aux[x.rank].left = x
 +
          x.child = aux[x.rank]
 +
          aux[x.rank] = ''null''         
 +
          x.rank = x.rank + 1
 +
      aux[x.rank] = x
 +
      '''if''' x.rank > max
 +
          max = x.rank 
 +
      x = next
 +
    <span style="color:#008000">// Собираем все корни обратно в тонкую кучу</span>
 +
    H = makeHeap()
 +
    i = 0
 +
    '''while''' i <= max
 +
      insert(H, aux[i])
 +
      i = i + 1
 +
    '''return''' tmp
 +
</code>
 +
 
 +
Пусть мы сделали <tex>ls</tex> связывающих шагов (англ. ''linking steps'') во время добавления в массив.
  
 
Мы удалили корень из списка за <tex>O(1)</tex>, затем за <tex>O(D(n))</tex> нормализовали детей корня и добавили в корневой список, далее за <tex>O(D(n))+ls</tex> получили новый корневой список, в котором за <tex>O(D(n))</tex> нашли минимальный корень и подвесили список за него.
 
Мы удалили корень из списка за <tex>O(1)</tex>, затем за <tex>O(D(n))</tex> нормализовали детей корня и добавили в корневой список, далее за <tex>O(D(n))+ls</tex> получили новый корневой список, в котором за <tex>O(D(n))</tex> нашли минимальный корень и подвесили список за него.
  
Получили фактическую стоимость <tex>O(D(n))+ls</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>.
+
Получили фактическую стоимость <tex>O(D(n))+ls</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>. Отсюда стоимость <tex>O(D(n))=O(\log(n))</tex>.
  
Cтоимость <tex>O(D(n))=O(\log(n))</tex>.
+
Стоимость <tex>O(\log(n))</tex>.
  
 
=== decreaseKey ===
 
=== decreaseKey ===
Строка 186: Строка 280:
 
# Ранг узла <tex>y</tex> на три больше, чем ранг его самого левого сына.
 
# Ранг узла <tex>y</tex> на три больше, чем ранг его самого левого сына.
 
# Ранг узла <tex>y</tex> равен двум, и он не имеет детей.
 
# Ранг узла <tex>y</tex> равен двум, и он не имеет детей.
# Узел <tex>y</tex> есть помеченный корень дерева.
+
# Узел <tex>y</tex> есть тонкий корень дерева.
  
 
Пусть узел <tex>y</tex> — это узел локализации братского нарушения.
 
Пусть узел <tex>y</tex> — это узел локализации братского нарушения.
* Узел <tex>y</tex> не помечен, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится помеченным, дерево становится корректным, процедура исправления завершается.
+
* Узел <tex>y</tex> не тонкий, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится тонким, дерево становится корректным, процедура исправления завершается.
* Узел <tex>y</tex> помечен, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
+
* Узел <tex>y</tex> тонкий, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
  
 
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
 
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
Строка 196: Строка 290:
 
Пусть узел <tex>y</tex> — это узел локализации родительского нарушения, а узел <tex>z</tex> — родитель узла <tex>y</tex>.
 
Пусть узел <tex>y</tex> — это узел локализации родительского нарушения, а узел <tex>z</tex> — родитель узла <tex>y</tex>.
  
Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>.  
+
Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>.
* Узел <tex>z</tex> не был помечен, пометим его, тогда дерево станет корректным.
+
# Если узел <tex>y</tex> не был старшим братом, то переходим к его левому брату, нарушение станет братским.
* Узел <tex>z</tex> был помечен, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
+
# Если узел <tex>y</tex> был старшим братом, то смотрим на родителя
 +
#* Узел <tex>z</tex> не был тонким, пометим его как тонкий, тогда дерево станет корректным.
 +
#* Узел <tex>z</tex> был тонким, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
  
 
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
 
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
  
Каждый промежуточный шаг рекурсии уменьшает количество помеченных узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>.
+
Каждый промежуточный шаг рекурсии уменьшает количество тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>. Также заметим, что мы всегда перемещаемся либо влево, либо вверх по нашему дереву, так что суммарно в худшем случае мы выполним <tex>O(\log(n))</tex> операций, а не <tex>O(n)</tex>, как в случае фибоначчиевой кучи.
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
  
 
=== delete ===
 
=== delete ===
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить <tex>decreaseKey</tex> этого элемента до <tex>-\infty</tex>, а затем выполнить <tex>extractMin</tex>.  
+
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить <tex>\mathtt{decreaseKey}</tex> этого элемента до <tex>-\infty</tex>, а затем выполнить <tex>\mathtt{extractMin}</tex>.  
 +
 
 +
<code>
 +
'''void''' delete(H: '''ThinHeap''', x: '''Node'''):
 +
    decreaseKey(H, x, <tex>-\infty</tex>)
 +
    extractMin()
 +
</code>
  
 
Стоимость <tex>O(\log(n))</tex>.
 
Стоимость <tex>O(\log(n))</tex>.
 
  
 
= Источники =
 
= Источники =
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи  — INTUIT.ru]
 
 
* [http://dl.acm.org/citation.cfm?id=1328914 ''Каплан Х.'', ''Тарьян А. Р..'', Thin Heaps, Thick Heaps // ACM Transactions on Algorithms. {{---}} 2008. {{---}} Т.4. {{---}} №1. {{---}} C. 1{{---}}14. {{---}} ISSN: 1549-6325]
 
* [http://dl.acm.org/citation.cfm?id=1328914 ''Каплан Х.'', ''Тарьян А. Р..'', Thin Heaps, Thick Heaps // ACM Transactions on Algorithms. {{---}} 2008. {{---}} Т.4. {{---}} №1. {{---}} C. 1{{---}}14. {{---}} ISSN: 1549-6325]
 
* [http://www.lektorium.tv/lecture/?id=14233 ''Станкевич А. С.'', Дополнительные главы алгоритмов, лекция 1 {{---}} Лекториум]
 
* [http://www.lektorium.tv/lecture/?id=14233 ''Станкевич А. С.'', Дополнительные главы алгоритмов, лекция 1 {{---}} Лекториум]
 +
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи  — INTUIT.ru]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Структуры данных]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]

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

Тонкая куча (англ. Thin heap) — структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фибоначчиева куча, но имеющая большую практическую ценность из-за меньших констант.

Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.

Тонкое дерево

Определение:
Тонкое дерево (англ. Thin tree) [math]T_k[/math] ранга [math]k[/math] — это дерево, которое может быть получено из биномиального дерева [math]B_k[/math] удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов.


Ограничение на принадлежность внутренним узлам вызвано тем, что у листьев детей нет, а если у корня [math]B_k[/math] удалить самого левого сына, то [math]B_k[/math] превратится в [math]B_{k-1}[/math].

Утверждение:
Ранг тонкого дерева равен количеству детей его корня.

Для любого узла [math]x[/math] в дереве [math]T_k[/math] обозначим:

  • [math]\mathtt{Degree(x)}[/math] — количество детей узла [math]x[/math].
  • [math]\mathtt{Rank(x)}[/math] — ранг соответствующего узла в биномиальном дереве [math]B_k[/math].

Свойства тонкого дерева

Утверждение:
Тонкое дерево обладает следующими свойствами:
  1. Для любого узла [math]x[/math] либо [math]\mathtt{Degree(x)=Rank(x)}[/math], в этом случае говорим, что узел [math]x[/math] не тонкий (полон); либо [math]\mathtt{Degree(x)=Rank(x)-1}[/math], в этом случае говорим, что узел [math]x[/math] тонкий (не полон).
  2. Корень не тонкий (полон).
  3. Для любого узла [math]x[/math] ранги его детей от самого правого к самому левому равны соответственно [math]\mathtt{0,1,2,...,Degree(x)-1}[/math].
  4. Узел [math]x[/math] тонкий тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
Из биномиального дерева ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются тонкими (не имеют самого левого сына)


Тонкая куча

Определение:
Тонкий лес (англ. Thin forest) — это набор тонких деревьев, ранги которых не обязательно попарно различны.


Утверждение:
Для любого натурального числа [math]n[/math] существует тонкий лес, который содержит ровно [math]n[/math] элементов и состоит из тонких деревьев попарно различных рангов.
[math]\triangleright[/math]
Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.
[math]\triangleleft[/math]


Определение:
Тонкая куча (англ. Thin heap) — это кучеобразно нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям кучи.


Пусть [math]D(n)[/math] — максимально возможный ранг узла в тонкой куче, содержащей [math]n[/math] элементов.

Теорема (О максимальном ранге узла):
В тонкой куче из [math]n[/math] элементов [math]D(n) \leqslant \log_{\Phi} n[/math], где [math]\varphi=\dfrac{1+\sqrt{5}}{2}[/math] — золотое сечение.
Доказательство:
[math]\triangleright[/math]

Сначала покажем, что узел ранга [math]k[/math] в тонком дереве имеет не менее [math]F_k \geqslant \varphi^{k-1}[/math] потомков, включая самого себя, где [math]F_k[/math][math]k[/math]-е число Фибоначчи.

Действительно, пусть [math]T_k[/math] — минимально возможное число узлов, включая самого себя, в тонком дереве ранга [math]k[/math]. По свойствам [math]1[/math] и [math]3[/math] тонкого дерева получаем следующие соотношения:

[math]T_0=1,T_1=1,T_k \geqslant 1+\sum\limits_{i=0}^{k-2}T_i[/math] для [math]k \geqslant 2[/math]

Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что [math]T_k \geqslant F_k[/math] для любых [math]k[/math]. Неравенство [math]F_k \geqslant \varphi^{k-1}[/math] хорошо известно.

Теперь убедимся в том, что максимально возможный ранг [math]D(n)[/math] тонкого дерева в тонкой куче, содержащей [math]n[/math] элементов, не превосходит числа [math]\log_{\varphi}(n)+1[/math].

Действительно, выберем в тонкой куче дерево максимального ранга. Пусть [math]n^*[/math] — количество вершин в этом дереве, тогда [math]n \geqslant n^* \geqslant \varphi^{D(n)-1}[/math].

Отсюда следует, что [math]D(n)\leqslant\log_{\varphi}(n)+1[/math].
[math]\triangleleft[/math]

Структура

Структура узла

struct Node
   int key      // ключ
   int rank     // ранг узла
   Node child   // указатель на самого левого ребенка узла
   Node right   // указатель на правого брата узла, либо на следующий корень, если текущий узел корень
   Node left    // указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень

Для ускорения проверки на тонкость (англ. thinness) можно отдельно хранить тонкость вершины. Также в вершине можно хранить любую дополнительную информацию.

Структура кучи

struct ThinHeap
   Node first   // указатель на корень дерева с минимальным ключом
   Node last    // указатель на последний корень

Операции над тонкой кучей

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

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

Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.

Для амортизационного анализа операций применим метод потенциалов.

Пусть функция потенциала определена как [math]\Phi = n + 2 \cdot m[/math] где [math]n[/math] — это количество тонких деревьев в куче, а [math]m[/math] — это количество тонких вершин.

Утверждение:
Определённый таким образом потенциал обладает свойствами:
  1. [math]\Phi \geqslant 0[/math].
  2. Для пустой тонкой кучи [math]\Phi = 0[/math].

Пусть [math]\mathtt{Node}[/math] — узел тонкого дерева, а [math]\mathtt{ThinHeap}[/math] — тонкая куча, причём [math]\mathtt{ThinHeap}[/math] содержит ссылки на первый и последний корень [math]\mathtt{first}[/math] и [math]\mathtt{last}[/math] соответственно.

Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла [math]x[/math] ранг равен [math]\mathtt{Degree(x) - 1}[/math].

bool isThin(x: Node):
  if x.rank == 1
     return x.child == null
  else
     return x.child.rank + 1 != x.rank

makeHeap

Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал [math]\Phi=0[/math].

ThinHeap makeHeap():
   H.first = null
   H.last = null  
   return H

Стоимость [math]O(1)[/math].

insert

Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла [math]x[/math] с ключом [math]x.key[/math], добавить его в корневой список на первое место, если этот ключ минимален, либо на последнее. Потенциал [math]\Phi[/math] увеличивается на 1.

void insert(H: ThinHeap, x: Node):
   if H.first == null
      H.first = x
      H.last = x
   else
      if x.key < H.first.key
         x.right = H.first
         H.first = x
      else
         H.last.right = x
         H.last = x  

Стоимость [math]O(1)[/math].

getMin

Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал [math]\Phi[/math] не меняется.

Node getMin(H: ThinHeap):
   return H.first

Стоимость [math]O(1)[/math].

merge

Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал [math]\Phi[/math] не меняется.

ThinHeap merge(H1: ThinHeap, H2: ThinHeap):
   if H1.first == null
      return H2
   else
      if H2.first == null
         return H1
      else 
         if H1.first.key < H2.first.key
            H1.last.right = H2.first
            H1.last = H2.last
            return H1
         else
            H2.last.right = H1.first
            H2.last = H1.last
            return H2

Стоимость [math]O(1)[/math].

extractMin

Чтобы извлечь минимальный элемент из тонкой кучи нужно:

  1. Удалить корень с минимальным ключом из корневого списка.
  2. Уменьшить ранг для всех его тонких детей.
  3. Cлить детей с корневым списком.
  4. Объединять, пока возможно, тонкие деревья одного ранга.

Это можно сделать, например, с помощью вспомогательного массива размером [math]O(D(n))[/math], в [math]i[/math]-ой ячейке которого хранится корень тонкого дерева [math]T_i[/math] ранга [math]i[/math].

Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.

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

Node extractMin(H: ThinHeap):
   // Удаляем минимальный корень из корневого списка
   tmp = H.first
   H.first = H.first.right
   if H.first == null
      H.last = null
   // Снимаем тонкость с его детей и добавляем их в корневой список
   x = tmp.first.child
   while x != null
      if isThin(x) 
         x.rank = x.rank - 1
      x.left = null
      next = x.right
      insert(H, x)
      x = next
   // Объединяем все корни одного ранга с помощью вспомогательного массива aux
   max = -1
   x = H.first
   while x != null
      while aux[x.rank] != null
         next = x.right
         if aux[x.rank].key < x.key
            swap(aux[x.rank], x)
         aux[x.rank].right = x.child
         x.child.left = aux[x.rank]
         aux[x.rank].left = x
         x.child = aux[x.rank]
         aux[x.rank] = null           
         x.rank = x.rank + 1
      aux[x.rank] = x
      if x.rank > max 
         max = x.rank   
      x = next
   // Собираем все корни обратно в тонкую кучу
   H = makeHeap()
   i = 0
   while i <= max
      insert(H, aux[i])
      i = i + 1
   return tmp

Пусть мы сделали [math]ls[/math] связывающих шагов (англ. linking steps) во время добавления в массив.

Мы удалили корень из списка за [math]O(1)[/math], затем за [math]O(D(n))[/math] нормализовали детей корня и добавили в корневой список, далее за [math]O(D(n))+ls[/math] получили новый корневой список, в котором за [math]O(D(n))[/math] нашли минимальный корень и подвесили список за него.

Получили фактическую стоимость [math]O(D(n))+ls[/math]. С другой стороны, при добавлении детей в список мы увеличили потенциал [math]\Phi[/math] не более чем на [math]O(D(n))[/math], а каждый связывающий шаг уменьшает наш потенциал [math]\Phi[/math] на [math]1[/math]. Отсюда стоимость [math]O(D(n))=O(\log(n))[/math].

Стоимость [math]O(\log(n))[/math].

decreaseKey

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

Теперь могут быть нарушены свойства тонкого дерева, будем различать два вида нарушений:

Назовем узел [math]y[/math] узлом локализации братского нарушения среди детей узла [math]z[/math], если ранг узла [math]y[/math] отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1.

Назовем узел [math]y[/math] узлом локализации родительского нарушения, если выполнено одно из трех условий:

  1. Ранг узла [math]y[/math] на три больше, чем ранг его самого левого сына.
  2. Ранг узла [math]y[/math] равен двум, и он не имеет детей.
  3. Узел [math]y[/math] есть тонкий корень дерева.

Пусть узел [math]y[/math] — это узел локализации братского нарушения.

  • Узел [math]y[/math] не тонкий, тогда помещаем поддерево с корнем в самом левом сыне узла [math]y[/math] на место пропущенного в братском списке. Узел [math]y[/math] становится тонким, дерево становится корректным, процедура исправления завершается.
  • Узел [math]y[/math] тонкий, тогда уменьшаем ранг узла [math]y[/math] на единицу. Теперь узлом локализации нарушения будет либо левый брат узла [math]y[/math], либо его родитель, тогда нарушение станет родительским.

С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.

Пусть узел [math]y[/math] — это узел локализации родительского нарушения, а узел [math]z[/math] — родитель узла [math]y[/math].

Переместим все поддерево с корнем в [math]y[/math] в корневой список и уменьшим ранг [math]y[/math].

  1. Если узел [math]y[/math] не был старшим братом, то переходим к его левому брату, нарушение станет братским.
  2. Если узел [math]y[/math] был старшим братом, то смотрим на родителя
    • Узел [math]z[/math] не был тонким, пометим его как тонкий, тогда дерево станет корректным.
    • Узел [math]z[/math] был тонким, тогда [math]z[/math] — новый узел локализации родительского нарушения, переходим к нему.

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

Каждый промежуточный шаг рекурсии уменьшает количество тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость [math]O(1)[/math]. Также заметим, что мы всегда перемещаемся либо влево, либо вверх по нашему дереву, так что суммарно в худшем случае мы выполним [math]O(\log(n))[/math] операций, а не [math]O(n)[/math], как в случае фибоначчиевой кучи.

Стоимость [math]O(1)[/math].

delete

Чтобы удалить элемент из тонкой кучи нужно сначала выполнить [math]\mathtt{decreaseKey}[/math] этого элемента до [math]-\infty[/math], а затем выполнить [math]\mathtt{extractMin}[/math].

void delete(H: ThinHeap, x: Node):
   decreaseKey(H, x, [math]-\infty[/math])
   extractMin() 

Стоимость [math]O(\log(n))[/math].

Источники