Изменения

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

''Тонкие кучи'', как и многие другие [[Двоичная куча|кучеобразные ]] структуры, аналогичны ''[[Биномиальная куча|биномиальным кучам'']].

|id=thin_tree_def. |definition='''Тонкое дерево''' (англ. ''thin 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>.  {{Утверждение|id=about_thin_tree_rank|statement=Ранг тонкого дерева равен количеству детей его корня.}}

Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим: * <tex>\mathtt{Degree(x)}</tex> {{---}} количество детей узла <tex>x</tex>; .* <tex>\mathtt{Rank(x)}</tex> {{---}} ранг соответствующего узла в [[Биномиальная куча#Биномиальное дерево|биномиальном дереве ]] <tex>B_k</tex>.

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

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

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

|id=about_thin_forest_with_n_nodes.

|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальный лес ]] является тонким, а для биномиального леса рассматриваемое утверждение справедливо.

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

|id=max_rank_th.

|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\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>F_0=1T_k</tex>{{---}} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>F_1=1k</tex>, . По свойствам <tex>F_k=F_{k-2}+F_{k-1}</tex> для и <tex>k \geqslant 23</tex>.тонкого дерева получаем следующие соотношения:

Действительно, пусть <tex>T_0=1,T_1=1,T_k</tex> \geqslant 1+\sum\limits_{i=0}^{k---}2} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>kT_i</tex>. По свойствам для <tex>1</tex> и <tex>3k \geqslant 2</tex> ''тонкого дерева'' получаем следующие соотношения:

Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_iF_k</tex> для любых <tex>k </tex>. Неравенство <tex>F_k \geqslant 2\varphi^{k-1}</tex>[[Фибоначчиева куча#Лемма3|хорошо известно]].

Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следуетТеперь убедимся в том, что максимально возможный ранг <tex>T_k \geqslant F_kD(n)</tex> для любых тонкого дерева в тонкой куче, содержащей <tex>kn</tex>. Неравенство элементов, не превосходит числа <tex>F_k \geqslant log_{\Phi^{k-varphi}(n)+1}</tex> хорошо известно.

Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> ''тонкого дерева'' в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phivarphi^{D(n)-1}</tex>.

Отсюда следует, что <tex>D(n)\leqslant\log_{\Phivarphi}(n)+1</tex>.

== Представление тонкой кучи Структура ===== Структура узла ===Поскольку при работе с '''struct'тонкой кучей'' ссылка на родителя требуется только у самого левого ее ребенка, можно хранить ее вместо ссылки на левого сына этой вершины. Node Таким образом, для эффективной работы '''int'тонкой кучи'' необходимы следующие поля узлаkey <span style="color:#008000"> // ключ</span>* '''int''' rank <texspan style="color:#008000">key // ранг узла</texspan> {{---}} ключ (вес) элемента;* '''Node''' child <texspan style="color:#008000">child< //tex> {{---}} указатель на самого левого ребенка узла;*<tex/span> '''Node''' right<span style="color:#008000"> //tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;*<tex/span> '''Node''' left<span style="color:#008000"> //tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это первый корень списка;*<tex>rank</texspan> {{---}} ранг узла (количество дочерних узлов данного узла). Отдельно должен храниться односвязный список корней, корень с минимальным ключом должне быть первым в этом списке.  Для ускорения проверки на ''тонкость'' (''thinness'') можно отдельно хранить помеченность вершины.

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

|id=about_thin_heap_potential.

# Для пустой тонкой кучи <tex>\Phi = 0</tex>.

Возвращаем новый пустой корневой список, его потенциал <texcode>\Phi '''ThinHeap''' makeHeap(): H.first = ''null'' H.last =0''null'' '''return''' H</texcode>.

Создаем Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла <tex>x</tex> с ключом <tex>x.key</tex>, добавляем добавить его в корневой список на первое место, если этот ключ минимален, иначе либо на второепоследнее. Потенциал <tex>\Phi</tex> увеличивается на 1. <code> '''void''' insert(H: '''ThinHeap''', x: '''Node'''): '''if''' H.first == ''null'' H.first = x H.last = x '''else''' '''if''' x.key < H.first.key x.right = H.first H.first = x '''else''' H.last.right = x H.last = x </code>

Обращаемся Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу спискаи вернуть его ключ, потенциал <tex>\Phi</tex> не меняется.  <code> '''Node''' getMin(H: '''ThinHeap'''): '''return''' H.first</code>

=== meld merge === Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.

Сливаем корневые списки<code> '''ThinHeap''' merge(H1: '''ThinHeap''', ставя первым тот список, где ключ первого корня минималенH2: '''ThinHeap'''): '''if''' H1.first == ''null'' '''return''' H2 '''else''' '''if''' H2.first == ''null'' '''return''' H1 '''else''' '''if''' H1.first. Суммарный потенциал key <tex>\PhiH2.first.key H1.last.right = H2.first H1.last = H2.last '''return''' H1 '''else''' H2.last.right = H1.first H2.last = H1.last '''return''' H2</texcode> не меняется.

# Удаляем корень с минимальным ключом из корневого списка.# Для всех его помеченных детей уменьшаем ранг и делаем их нормальными.# Cливаем детей с корневым списком.# Объединяем, пока возможно, тонкие деревья одного ранга.Это можно сделать, например, с помощью вспомогательного массива размером <tex>O(D(n))</tex>, в <tex>i</tex>-ой ячейке которго которого хранится корень тонкого дерева <tex>T_i</tex> ранга <tex>i</tex>.

При добавлении нового дерева мы, пока возможноесли дерево такого ранга уже есть в массиве, связываем его с деревом такого же ранга, а затем существующим и пытаемся добавить новое дерево с рангом на <tex>1</tex> больше. <code> '''Node''' extractMin(H: '''ThinHeap'''): <span style="color:#008000">// Удаляем минимальный корень из корневого списка</span> tmp = H.first H.first = H.first.right '''if''' H.first == ''null'' H.last = ''null'' <span style="color:#008000">// Снимаем тонкость с его детей и добавляем их в корневой список</span> x = tmp.first.child '''while''' x != ''null'' '''if''' isThin(x) x.rank = x.rank - 1 x.left = ''null'' next = x.right insert(H, x) x = next <span style="color:#008000">// Объединяем все корни одного ранга с помощью вспомогательного массива aux</span> max = -1 x = H.first '''while''' x != ''null'' '''while''' aux[x.rank] != ''null'' next = x.right '''if''' aux[x.rank].key < x.key swap(aux[x.rank], x) aux[x.rank].right = x.child x.child.left = aux[x.rank] aux[x.rank].left = x x.child = aux[x.rank] aux[x.rank] = ''null'' x.rank = x.rank + 1 aux[x.rank] = x '''if''' x.rank > max max = x.rank x = next <span style="color:#008000">// Собираем все корни обратно в тонкую кучу</span> H = makeHeap() i = 0 '''while''' i <= max insert(H, aux[i]) i = i + 1 '''return''' tmp</code>

Пусть мы сделали <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>. Отсюда стоимость <tex>O(D(n))=O(\log(n))</tex>.

Cтоимость Стоимость <tex>O(D(n))=O(\log(n))</tex>.

Сначала выполняем Чтобы удалить элемент из тонкой кучи нужно сначала выполнить <tex>\mathtt{decreaseKey}</tex> этого элемента до <tex>-\infty</tex>, а затем выполняем выполнить <tex>\mathtt{extractMin}</tex>.  <code> '''void''' delete(H: '''ThinHeap''', x: '''Node'''): decreaseKey(H, x, <tex>-\infty</tex>) extractMin() </code>