120
правок
Изменения
Нет описания правки
'''''Тонкая куча''''' — {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и ''фиббоначиева куча'', но имеющая большую практическую ценность из-за меньших констант.
''Тонкие кучи'', как и многие другие кучеобразные структуры, аналогичны ''биномиальным кучам''.
= Тонкое дерево =
{{Определение
|id=def1thin_tree_def. |definition='''Тонкое дерево''' (''thin tree'') <tex>T_k</tex> ранга <tex>k</tex> — {{---}} это дерево, которое может быть получено из биномиального дерева <tex>B_k</tex> удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.
}}
Заметим, что у листьев детей нет, а если у корня <tex>B_k</tex> удалить самого левого сына, то <tex>B_k</tex> превратится в <tex>B_{k-1}</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_node_degrees.
|statement=Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полный); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (неполный).
}}
{{Утверждение
|id=about_root.
|statement=Корень не помечен (полный).
}}
{{Утверждение
|id=about_children_ranks.
|statement=Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
}}
{{Утверждение
|id=proposal1about_marked_nodes. |about=Свойства тонкого дерева|statement=1)Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полный); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (неполный).<br>2)Корень не помечен (полный).<br>3)Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.<br>4)Узел <tex>x</tex> помечен тогда и только тогда, если его ранг на <tex>2</tex> больше, чем ранг его самого левого сына, или его ранг равен <tex>1</tex> и он не имеет детей.<br>
}}
= Тонкая куча =
{{Определение
|id=def1thin_forest_def. |definition='''Тонкий лес''' — {{---}} это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.
}}
{{Определение
|id=def1thin_heap_def. |definition='''Тонкая куча''' — (''thin heap'') {{---}} это кучеобразно нагруженный ''тонкий лес''.
}}
{{Утверждение
|id=proposal2about_thin_forest_with_n_nodes.
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
|proof=Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.
}}
Пусть <tex>D(n)</tex> — {{---}} максимально возможный ранг узла в тонкой куче, содержащей <tex>n</tex> элементов.
{{Теорема
|id=th1max_rank_th.
|about=О максимальном ранге узла
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex>\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> хорошо известно.
Теперь убедимся в том, что максимально возможный ранг <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>D(n)\leqslant\log_{\Phi}(n)+1</tex>.
}}
= Источники =
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи — INTUIT.ru]
* [http://pdf.aminer.org/000/268/108/heaps_on_heaps.pdf Haim Kaplan, Robert E. Tarjan Thin Heaps, Thick Heaps ACM Transactions on Algorithms - TALG , vol. 4, no. 1, pp. 1-14, 2008]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
