120
правок
Изменения
Добавлены ссылки
[[Файл:Thin heap examples.png|200x200px|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева ]] ранга 3 получены два тонких дерева. Числа обозначают ранг вершин, черные вершины являются помеченными (не имеют самого левого сына).]]'''''Тонкая куча''''' {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча|''фиббоначиева фибоначчиева куча'']], но имеющая большую практическую ценность из-за меньших констант.
''Тонкие кучи'', как и многие другие [[Двоичная куча|кучеобразные ]] структуры, аналогичны [[Биномиальная куча|''биномиальным кучам'']].
= Тонкое дерево =
{{Определение
|id=thin_tree_def.
|definition='''Тонкое дерево''' (''thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева ]] <tex>B_k</tex> удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.
}}
Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим:
* <tex>Degree(x)</tex> {{---}} количество детей узла <tex>x</tex>.
* <tex>Rank(x)</tex> {{---}} ранг соответствующего узла в [[Биномиальная куча#Биномиальное дерево|биномиальном дереве ]] <tex>B_k</tex>.
== Свойства тонкого дерева ==
|id=about_thin_forest_with_n_nodes.
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальный ]] лес является тонким, а для [[Биномиальная куча#Биномиальное дерево|биномиального ]] леса рассматриваемое утверждение справедливо.
}}
{{Определение
|id=thin_heap_def.
|definition='''Тонкая куча''' (''thin heap'') {{---}} это [[Двоичная куча|кучеобразно ]] нагруженный ''тонкий лес''.
}}
== Представление тонкой кучи ==
''Тонкую кучу'' можно представить как [[Список#Односвязный список|односвязный список ]] корней ''тонких деревьев'', причем корень с минимальным ключом должен быть первым в списке.
Поскольку при работе с ''тонкой кучей'' ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины.
Также в вершине можно хранить любую дополнительную информацию.
Для работы с ''тонкой кучей'' достаточно иметь ссылку на [[Список#Односвязный список|односвязный список]] ее первый коренькорней.
== Операции над тонкой кучей ==
|}
Многие операции над ''тонкой кучей'' выполняются так же, как и над [[Фибоначчиева куча|''фиббоначиевой'']].
Для [[Амортизационный анализ|амортизационного анализа ]] операций применим [[Амортизационный анализ#Метод потенциалов|метод потенциалов]].
Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество ''тонких деревьев'' в куче, а <tex>m</tex> {{---}} это количество помеченных вершин.
# Для пустой ''тонкой кучи'' <tex>\Phi = 0</tex>.
}}
=== makeHeap ===
Стоимость <tex>O(1)</tex>.
=== insert ===
Стоимость <tex>O(1)</tex>.
=== getMin ===
Стоимость <tex>O(1)</tex>.
=== meld ===
Стоимость <tex>O(1)</tex>.
=== extractMin ===
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
# Удалить корень с минимальным ключом из корневого списка.
# Уменьшить ранг для всех его помеченных детей.
# Cлить детей с корневым списком.
# Объединять, пока возможно, тонкие деревья одного ранга.
Это можно сделать, например, с помощью вспомогательного массива размером <tex>O(D(n))</tex>, в <tex>i</tex>-ой ячейке которого хранится корень тонкого дерева <tex>T_i</tex> ранга <tex>i</tex>.
=== decreaseKey ===
Чтобы уменьшить ключ элемента нужно:
Стоимость <tex>O(1)</tex>.
=== delete ===
Стоимость <tex>O(\log(n))</tex>.
