Изменения
Нет описания правки
'''Тонкая куча''Тонкая куча'(англ. ''Thin heap'' — это ) {{---}} структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и ''фиббоначиева [[Фибоначчиева куча|фибоначчиева куча'']], но имеющая большую практическую ценность из-за меньших констант. Тонкие кучи, как и многие другие [[Двоичная куча|кучеобразные]] структуры, аналогичны [[Биномиальная куча|биномиальным кучам]].= Тонкое дерево =
{{Определение
|id=def1. 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>\mathtt{Degree(x)}</tex> {{---}} количество детей узла <tex>x</tex>.
* <tex>\mathtt{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>
}}
{{Определение
|id=def1. thin_forest_def|definition='''Тонкая кучаТонкий лес''' — это кучеобразно нагруженный (англ. ''тонкий лесThin forest'') {{---}} это набор тонких деревьев, ранги которых не обязательно попарно различны.
}}
{{Утверждение
|id=proposal2. about_thin_forest_with_n_nodes
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальный лес ]] является тонким, а для биномиального леса рассматриваемое утверждение справедливо.}} {{Определение|id=thin_heap_def|definition='''Тонкая куча''' (англ. ''Thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям [[Двоичная куча|кучи]].
}}
Пусть <tex>D(n)</tex> — {{---}} максимально возможный ранг узла в тонкой куче, содержащей <tex>n</tex> элементов.
{{Теорема
|id=th1. max_rank_th
|about=О максимальном ранге узла
|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>== Операции над тонкой кучей == Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
}}
Пусть <tex>\mathtt{Node}</tex> {{---}} узел тонкого дерева, а <tex>\mathtt{ThinHeap}</tex> {{---}} тонкая куча, причём <tex>\mathtt{ThinHeap}</tex> содержит ссылки на первый и последний корень <tex>\mathtt{first}</tex> и <tex>\mathtt{last}</tex> соответственно.
Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>\mathtt{Degree(x) - 1}</tex>.
<code>
'''bool''' isThin(x: '''Node'''):
'''if''' x.rank == 1
'''return''' x.child == ''null''
'''else'''
'''return''' x.child.rank + 1 != x.rank
</code>
=== makeHeap ===
Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
<code>
'''ThinHeap''' makeHeap():
H.first = ''null''
H.last = ''null''
'''return''' H
</code>
Стоимость <tex>O(1)</tex>.
=== insert ===
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла <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>O(1)</tex>.
=== getMin ===
Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал <tex>\Phi</tex> не меняется.
<code>
'''Node''' getMin(H: '''ThinHeap'''):
'''return''' H.first
</code>
Стоимость <tex>O(1)</tex>.
=== 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 < H2.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
</code>
Стоимость <tex>O(1)</tex>.
=== extractMin ===
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
# Удалить корень с минимальным ключом из корневого списка.
# Уменьшить ранг для всех его тонких детей.
# 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))+ls</tex> получили новый корневой список, в котором за <tex>O(D(n))</tex> нашли минимальный корень и подвесили список за него.
Получили фактическую стоимость <tex>O(D(n))+ls</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>. Отсюда стоимость <tex>O(D(n))=O(\log(n))</tex>.
Стоимость <tex>O(\log(n))</tex>.
=== decreaseKey ===
После уменьшения ключа может быть нарушена [[Двоичная куча|кучеобразность]], в этом случае мы переносим все поддерево с корнем в уменьшаемом элементе в корневой список, также обновляем минимум в тонкой куче.
Теперь могут быть нарушены свойства тонкого дерева, будем различать два вида нарушений:
* Братские нарушения {{---}} это нарушения [[Тонкая куча#about_thin_tree|третьего свойства]] тонкого дерева.
* Родительские нарушения {{---}} это нарушения [[Тонкая куча#about_thin_tree|первого или второго свойства]] тонкого дерева.
Назовем узел <tex>y</tex> узлом локализации братского нарушения среди детей узла <tex>z</tex>, если ранг узла <tex>y</tex> отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1.
Назовем узел <tex>y</tex> узлом локализации родительского нарушения, если выполнено одно из трех условий:
# Ранг узла <tex>y</tex> на три больше, чем ранг его самого левого сына.
# Ранг узла <tex>y</tex> равен двум, и он не имеет детей.
# Узел <tex>y</tex> есть тонкий корень дерева.
Пусть узел <tex>y</tex> — это узел локализации братского нарушения.
* Узел <tex>y</tex> не тонкий, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится тонким, дерево становится корректным, процедура исправления завершается.
* Узел <tex>y</tex> тонкий, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
Пусть узел <tex>y</tex> — это узел локализации родительского нарушения, а узел <tex>z</tex> — родитель узла <tex>y</tex>.
Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>.
# Если узел <tex>y</tex> не был старшим братом, то переходим к его левому брату, нарушение станет братским.
# Если узел <tex>y</tex> был старшим братом, то смотрим на родителя
#* Узел <tex>z</tex> не был тонким, пометим его как тонкий, тогда дерево станет корректным.
#* Узел <tex>z</tex> был тонким, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
Каждый промежуточный шаг рекурсии уменьшает количество тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>. Также заметим, что мы всегда перемещаемся либо влево, либо вверх по нашему дереву, так что суммарно в худшем случае мы выполним <tex>O(\log(n))</tex> операций, а не <tex>O(n)</tex>, как в случае фибоначчиевой кучи.
Стоимость <tex>O(1)</tex>.
=== delete ===
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить <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>
Стоимость <tex>O(\log(n))</tex>.
= Источники =
* [http://dl.acm.org/citation.cfm?id=1328914 ''Каплан Х.'', ''Тарьян А. Р..'', Thin Heaps, Thick Heaps // ACM Transactions on Algorithms. {{---}} 2008. {{---}} Т.4. {{---}} №1. {{---}} C. 1{{---}}14. {{---}} ISSN: 1549-6325]
* [http://www.lektorium.tv/lecture/?id=14233 ''Станкевич А. С.'', Дополнительные главы алгоритмов, лекция 1 {{---}} Лекториум]
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи — INTUIT.ru]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория: Приоритетные очереди]]