120
правок
Изменения
м
''Тонкие кучи'', как и многие другие [[Двоичная куча|кучеобразные]] структуры, аналогичны [[Биномиальная куча|''биномиальным кучам'']].
''Тонкую кучу'' можно представить как [[Список#Односвязный список|односвязный список]] корней ''тонких деревьев'', причем корень с минимальным ключом должен быть первым в списке.
Нет описания правки
[[Файл:Thin heap examples.png|200x200px|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранг вершин, черные вершины являются помеченными (не имеют самого левого сына).]]
'''''Тонкая куча''''' {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча|''фибоначчиева куча'']], но имеющая большую практическую ценность из-за меньших констант.
= Тонкое дерево =
|id=about_thin_tree
|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>0,1,2,...,Degree(x)-1</tex>.
# Узел <tex>x</tex> помечен тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
{{Определение
|id=thin_forest_def
|definition='''Тонкий лес''' (''thin forest'') {{---}} это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.
}}
|id=about_thin_forest_with_n_nodes
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальныйлес]] лес является тонким, а для [[Биномиальная куча#Биномиальное дерево|биномиального]] леса рассматриваемое утверждение справедливо.
}}
{{Определение
|id=thin_heap_def
|definition='''Тонкая куча''' (''thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный ''тонкий лес'', то есть значение в любой вершине тонкого дерева не превосходит значений в её потомках.
}}
|about=О максимальном ранге узла
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phi=\frac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \Phi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи, определяемое соотношениями <tex>F_0=1</tex>, <tex>F_1=1</tex>, <tex>F_k=F_{k-2}+F_{k-1}</tex> для <tex>k \geqslant 2</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_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \Phi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> ''тонкого дерева'' в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>.
Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n)-1}</tex>.
== Представление тонкой кучи ==
Поскольку при работе с ''тонкой кучей'' ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины.
Таким образом, для эффективной работы ''тонкой кучи'' необходимы следующие поля узла:
*<tex>key</tex> {{---}} ключ (вес) элемента;
*<tex>child</tex> {{---}} указатель на самого левого ребенка узла;
*<tex>rank</tex> {{---}} ранг узла (количество дочерних узлов данного узла).
Для ускорения проверки на ''тонкость'' (''thinness'') можно отдельно хранить помеченность вершины.
Также в вершине можно хранить любую дополнительную информацию.
Для работы с ''тонкой кучей'' достаточно иметь [[Список#Односвязный список|односвязный список]] ее корней.
== Операции над тонкой кучей ==
Рассмотрим операции, которые можно производить над ''тонкой кучей''. Время работы указано в таблице:
{| border="1"
|-align="center"
|}
Многие операции над ''тонкой кучей'' выполняются так же, как и над [[Фибоначчиева куча|''фиббоначиевой'']].
Для [[Амортизационный анализ|амортизационного анализа]] операций применим [[Амортизационный анализ#Метод потенциалов|метод потенциалов]].
Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество ''тонких деревьев'' в куче, а <tex>m</tex> {{---}} это количество помеченных вершин.
{{Утверждение
|statement=Определённый таким образом потенциал обладает свойствами:
# <tex>\Phi \geqslant 0</tex>.
# Для пустой ''тонкой кучи'' <tex>\Phi = 0</tex>.
}}
Пусть мы сделали <tex>ls</tex> связывающих шагов (''linking steps'') во время добавления в массив.
Мы удалили корень из списка за <tex>O(1)</tex>, затем за <tex>O(D(n))</tex> нормализовали детей корня и добавили в корневой список, далее за <tex>O(D(n))+O(ls)</tex> получили новый корневой список, в котором за <tex>O(D(n))</tex> нашли минимальный корень и подвесили список за него.
Получили фактическую стоимость <tex>O(D(n))+O(ls)</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>.
Cтоимость <tex>O(D(n))=O(\log(n))</tex>.
