Изменения

'''Тонкая куча''Тонкая куча'(англ. ''Thin heap'' — это ) {{---}} структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и ''фиббоначиева [[Фибоначчиева куча|фибоначчиева куча'']], но имеющая большую практическую ценность из-за меньших констант. Тонкие кучи, как и многие другие [[Двоичная куча|кучеобразные]] структуры, аналогичны [[Биномиальная куча|биномиальным кучам]].= Тонкое дерево =

|id=def1. thin_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> — количество {{Утверждение|id=about_thin_tree_rank|statement=Ранг тонкого дерева равен количеству детей узла <tex>x</tex>; <tex>Rank(x)</tex> — ранг соответствующего узла в биномиальном дереве <tex>B_k</tex>его корня.}}

|id=proposal1. about_thin_tree|aboutstatement=Свойства тонкого дереваТонкое дерево обладает следующими свойствами:|statement=1)# Для любого узла <tex>x</tex> либо <tex>\mathtt{Degree(x)=Rank(x)}</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен тонкий (полныйполон); либо <tex>\mathtt{Degree(x)=Rank(x)-1}</tex>, в этом случае говорим, что узел <tex>x</tex> помечен тонкий (неполныйне полон).<br>2)# Корень не помечен тонкий (полныйполон).<br>3)# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>\mathtt{0,1,2,...,Degree(x)-1}</tex>.<br>4)# Узел <tex>x</tex> помечен тонкий тогда и только тогда, если когда его ранг на <tex>2</tex> больше, чем ранг его самого левого сына, или его ранг равен <tex>1</tex> , и он не имеет детей.<br>

{{Определение[[Файл:Thin_trees.png|200x200px|слева|frame|id=def1. Из [[Биномиальная куча#Биномиальное дерево|definition='''Тонкий лес''' — это набор ''биномиального дерева]] ранга 3 получены два тонких деревьев''дерева. Числа обозначают ранги узлов, ранги которых закрашенные вершины являются тонкими (не обязательно попарно различны.имеют самого левого сына)]]<br clear="all" /> }}== Тонкая куча ==

|id=def1. thin_forest_def|definition='''Тонкая кучаТонкий лес''' — это кучеобразно нагруженный (англ. ''тонкий лесThin forest'') {{---}} это набор тонких деревьев, ранги которых не обязательно попарно различны.

|id=proposal2. about_thin_forest_with_n_nodes

|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальный лес ]] является тонким, а для биномиального леса рассматриваемое утверждение справедливо.}} {{Определение|id=thin_heap_def|definition='''Тонкая куча''' (англ. ''Thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям [[Двоичная куча|кучи]].

Пусть <tex>D(n)</tex> — {{---}} максимально возможный ранг узла в тонкой куче, содержащей <tex>n</tex> элементов.

|id=th1. max_rank_th

|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex>\Phivarphi=\fracdfrac{1+\sqrt{5}}{2}</tex> — {{---}} золотое сечение.|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \Phivarphi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи. Действительно, определяемое соотношениями пусть <tex>T_k</tex> {{---}} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>k</tex>. По свойствам <tex>F_0=1</tex>, и <tex>3</tex> тонкого дерева получаем следующие соотношения: <tex>F_1T_0=1,T_1=1,T_k \geqslant 1+\sum\limits_{i=0}^{k-2}T_i</tex>для <tex>k \geqslant 2</tex> Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k=F_</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \varphi^{k-21}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]]. Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> тонкого дерева в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\varphi}(n)+F_1</tex>.  Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {k{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \varphi^{D(n)-1}</tex> для . Отсюда следует, что <tex>k D(n)\leqslant\log_{\geqslant 2varphi}(n)+1</tex>.}} == Структура ===== Структура узла === '''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> Для ускорения проверки на тонкость (англ. ''thinness'') можно отдельно хранить тонкость вершины.Также в вершине можно хранить любую дополнительную информацию. === Структура кучи === '''struct''' ThinHeap '''Node''' first <span style="color:#008000"> // указатель на корень дерева с минимальным ключом</span> '''Node''' last <span style="color:#008000"> // указатель на последний корень</span>== Операции над тонкой кучей == Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:

Действительно, пусть {| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF! Операция || Время работы |-align="center" bgcolor=#FFFFFF|<tex>\mathrm{makeHeap}</tex>T_k||<tex>O(1)</tex> — минимально возможное число узлов, включая самого себя, в тонком дереве ранга |-align="center" bgcolor=#FFFFFF|<tex>k\mathrm{insert}</tex>. По свойствам ||<tex>O(1)</tex>|-align="center" bgcolor=#FFFFFF||<tex>\mathrm{getMin}</tex> и ||<tex>3O(1)</tex> ''тонкого дерева'' получаем следующие соотношения:|-align="center" bgcolor=#FFFFFF|<tex>\mathrm{merge}</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>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(\Phi = n)+ 2 \cdot m</tex> ''тонкого дерева'' в тонкой куче, содержащей где <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi{---}}(n)+1</tex>. Действительно, выберем это количество тонких деревьев в тонкой куче дерево максимального ранга. Пусть , а <tex>n^*m</tex> — количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n){---1}</tex>} это количество тонких вершин.

Отсюда следует, что {{Утверждение|id=about_thin_heap_potential|statement=Определённый таким образом потенциал обладает свойствами:# <tex>D(n)\leqslantPhi \log_{geqslant 0</tex>.# Для пустой тонкой кучи <tex>\Phi}(n)+1= 0</tex>.