27
правок
Изменения
Нет описания правки
'''Тонкая куча''Тонкая куча'(англ. ''Thin heap'' ) {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
Тонкие кучи, как и многие другие [[Двоичная куча|кучеобразные]] структуры, аналогичны [[Биномиальная куча|биномиальным кучам]].
{{Определение
|id=thin_tree_def
|definition='''Тонкое дерево''' (англ. ''thin Thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов.
}}
Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим:
* <tex>\mathtt{Degree(x)}</tex> {{---}} количество детей узла <tex>x</tex>.* <tex>\mathtt{Rank(x)}</tex> {{---}} ранг соответствующего узла в [[Биномиальная куча#Биномиальное дерево|биномиальном дереве]] <tex>B_k</tex>.
== Свойства тонкого дерева ==
|id=about_thin_tree
|statement=Тонкое дерево обладает следующими свойствами:
# Для любого узла <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, и он не имеет детей.
}}
{{Определение
|id=thin_forest_def
|definition='''Тонкий лес''' (англ. ''thin Thin forest'') {{---}} это набор тонких деревьев, ранги которых не обязательно попарно различны.
}}
{{Определение
|id=thin_heap_def
|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>
Также в вершине можно хранить любую дополнительную информацию.
== Операции над тонкой кучей ==
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
{| 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>.
<code>
'''bool ''' isThin(x) '''if ''' x.rank == 1 '''return ''' x.child == null '''else''' '''return ''' x.child.rank + 1 != x.rank
</code>
<code>
'''ThinHeap ''' makeHeap()
H.first = null
H.last = null
'''return ''' H;
</code>
<code>
'''void ''' insert(H, x) '''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>
'''Node ''' getMin(H) '''return ''' H.first
</code>
<code>
'''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
H1.last.right = H2.first
H1.last = H2.last
'''return ''' H1 '''else'''
H2.last.right = H1.first
H2.last = H1.last
'''return ''' H2
</code>
<code>
'''Node ''' extractMin(H) <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
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.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> нашли минимальный корень и подвесили список за него.
=== delete ===
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить <tex>\mathtt{decreaseKey}</tex> этого элемента до <tex>-\infty</tex>, а затем выполнить <tex>\mathtt{extractMin}</tex>.
<code>
'''void ''' delete(H, x)
decreaseKey(H, x, <tex>-\infty</tex>)
extractMin()
