Изменения

'''Тонкая куча''Тонкая куча'(англ. ''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>.

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

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

== Представление тонкой кучи Структура ===== Структура узла === '''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>\mathrm{meld}</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>\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>.

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

'''ThinHeap ''' makeHeap()

'''return ''' H;

'''void ''' insert(H, x) '''if ''' H.first == null

'''else''' '''if ''' x.key < H.first.key

'''else'''

'''Node ''' getMin(H) '''return ''' H.first

'''ThinHeap ''' meld(H1, H2) '''if ''' H1.first == null '''return ''' H2 '''else ''' '''if ''' H2.first == null '''return ''' H1 '''else ''' '''if ''' H1.first.key < H2.first.key

'''return ''' H1 '''else'''

'''return ''' H2

'''Node ''' extractMin(H) <span style="color:#008000">// Удаляем минимальный корень из корневого списка</span>

'''if ''' H.first == null H.last = null <span style="color:#008000">// Снимаем тонкость с его детей и добавляем их в корневой список </span>

'''while ''' x != null '''if ''' isThin(x)

<span style="color:#008000">// Объединяем все корни одного ранга с помощью вспомогательного массива aux</span>

'''while ''' x != null '''while ''' aux[x.rank] != null

'''if ''' aux[x.rank].key < x.key

'''if ''' x.rank > max

<span style="color:#008000">// Собираем все корни обратно в тонкую кучу</span>

'''while ''' i <= max

'''return ''' tmp

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

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

'''void ''' delete(H, x)