Изменения

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

|definition='''Тонкое дерево''' (англ. ''thin Thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов.

* <tex>\mathtt{Degree(x)}</tex> {{---}} количество детей узла <tex>x</tex>.* <tex>\mathtt{Rank(x)}</tex> {{---}} ранг соответствующего узла в [[Биномиальная куча#Биномиальное дерево|биномиальном дереве]] <tex>B_k</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>\mathtt{0,1,2,...,Degree(x)-1}</tex>.# Узел <tex>x</tex> помечен тонкий тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.

[[Файл:Thin_tree_examplesThin_trees.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются помеченными тонкими (не имеют самого левого сына)]]

== Тонкая куча ==

|definition='''Тонкий лес''' (англ. ''thin Thin forest'') {{---}} это набор тонких деревьев, ранги которых не обязательно попарно различны.

|definition='''Тонкая куча''' (англ. ''thin Thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям [[Двоичная куча|кучи]].

|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phivarphi=\fracdfrac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \Phivarphi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи.

<tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_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 \Phivarphi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].

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

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

Отсюда следует, что <tex>D(n)\leqslant\log_{\Phivarphi}(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>

Тонкую кучу можно представить как [[Список#Односвязный список|односвязный список]] корней тонких деревьев, причем корень с минимальным ключом должен быть первым в списке. Поскольку при работе с тонкой кучей ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины.  Таким образом, для эффективной работы тонкой кучи необходимы следующие поля узла:*<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>

 {| class="wikitable" style="width:10cm" border=1|+|-align="1center"bgcolor=#EEEEFF! Операция || Время работы |-align="center"bgcolor=#FFFFFF |<tex>\mathrm{makeHeap}</tex> ||<tex>O(1)</tex> |-align="center"bgcolor=#FFFFFF |<tex>\mathrm{insert}</tex> ||<tex>O(1)</tex> |-align="center"bgcolor=#FFFFFF ||<tex>\mathrm{getMin}</tex> ||<tex>O(1)</tex> |-align="center"bgcolor=#FFFFFF |<tex>meld\mathrm{merge}</tex> ||<tex>O(1)</tex> |-align="center"bgcolor=#FFFFFF |<tex>\mathrm{extractMin}</tex> ||<tex>O(\log(n))</tex> |-align="center"bgcolor=#FFFFFF |<tex>\mathrm{decreaseKey}</tex> ||<tex>O(1)</tex> |-align="center"bgcolor=#FFFFFF |<tex>\mathrm{delete}</tex> ||<tex>O(\log(n))</tex> |}

Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество тонких деревьев в куче, а <tex>m</tex> {{---}} это количество помеченных тонких вершин.

Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла <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>

=== meld merge ===

# Уменьшить ранг для всех его помеченных тонких детей.

<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(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>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>z</tex> не был помечентонким, пометим егокак тонкий, тогда дерево станет корректным.#* Узел <tex>z</tex> был помечентонким, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.

Каждый промежуточный шаг рекурсии уменьшает количество помеченных тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>. Также заметим, что мы всегда перемещаемся либо влево, либо вверх по нашему дереву, так что суммарно в худшем случае мы выполним <tex>O(\log(n))</tex> операций, а не <tex>O(n)</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>