120
правок
Изменения
Нет описания правки
{{Определение
|id=thin_forest_def.
|definition='''Тонкий лес''' (''thin forest'') {{---}} это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.
}}
{{Утверждение
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
|proof=Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.
}}
{{Определение
|id=thin_heap_def.
|definition='''Тонкая куча''' (''thin heap'') {{---}} это кучеобразно нагруженный ''тонкий лес''.
}}
|id=max_rank_th.
|about=О максимальном ранге узла
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <texdpi = "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>D(n)\leqslant\log_{\Phi}(n)+1</tex>.
}}
== Представление тонкой кучи ==
Поскольку при работе с ''тонкой кучей'' ссылка на родителя требуется только у самого левого ее ребенка, можно хранить ее вместо ссылки на левого сына этой вершины.
Таким образом, для эффективной работы ''тонкой кучи'' необходимы следующие поля узла:
*<tex>key</tex> {{---}} ключ (вес) элемента;
*<tex>child</tex> {{---}} указатель на самого левого ребенка узла;
*<tex>right</tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
*<tex>left</tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это первый корень списка;
*<tex>rank</tex> {{---}} ранг узла (количество дочерних узлов данного узла).
Отдельно должен храниться односвязный список корней, корень с минимальным ключом должне быть первым в этом списке.
Для ускорения проверки на ''тонкость'' (''thinness'') можно отдельно хранить помеченность вершины.
Также в вершине можно хранить любую дополнительную информацию.
== Операции над тонкой кучей ==
Рассмотрим операции, которые можно производить с тонкой кучей. Время работы указано в таблице:
{| border="1"
|-align="center"
|<tex>makeHeap</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>insert</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>getMin</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>meld</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>extractMin</tex>
|<tex>O(\log(n))</tex>
|-align="center"
|<tex>decreaseKey</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>delete</tex>
|<tex>O(\log(n))</tex>
|}
Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.
=== makeHeap ===
Возвращаем новый пустой корневой список. Время <tex>O(1)</tex>.
=== insert ===
Создаем новое тонкое дерево из единственного узла с ключом <tex>x</tex>, добавляем в корневой список на первое место, если ключ минимален, иначе на второе. Время <tex>O(1)</tex>.
=== getMin ===
Обращаемся к первому корневому узлу списка. Время <tex>O(1)</tex>.
=== meld ===
Сливаем корневые списки, ставя первым тот список, где ключ первого корня минимален. Время <tex>O(1)</tex>.
=== extractMin ===
Удаляем корень с минимальным ключом из корневого списка, затем для всех его тонких детей уменьшаем ранг и делаем их нормальными, после чего сливаем детей с корневым списком и объединяем, пока возможно, тонкие деревья одного ранга.
Время <tex>O(\log(n))</tex>.
=== decreaseKey ===
Время <tex>O(1)</tex>.
=== delete ===
Сначала выполняем <tex>decreaseKey</tex> этого элемента до <tex>-\infty</tex>, затем выполняем <tex>extractMin</tex>. Время <tex>O(\log(n))</tex>.
= Источники =
