1632
правки
Изменения
м
Тонкую кучу можно представить как [[Список#Односвязный список|односвязный список]] корней тонких деревьев, причем корень с минимальным ключом должен быть первым в списке. Поскольку при работе с тонкой кучей ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины. Таким образом, для эффективной работы тонкой кучи необходимы следующие поля узла:*<tex>key</tex> {{---}} ключ (вес) элемента;*<tex>child</tex> {{---}} указатель на самого левого ребенка узла;*<tex>right</tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;*<tex>left</tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень;*<tex>rank</tex> {{---}} ранг узла. Для ускорения проверки на тонкость (англ. ''thinness'') можно отдельно хранить тонкость вершины.
Для работы === Структура кучи === '''struct''' ThinHeap '''Node''' first <span style="color:#008000"> // указатель на корень дерева с тонкой кучей достаточно иметь [[Списокминимальным ключом</span> '''Node''' last <span style="color:#Односвязный список|односвязный список]] ее корней.008000"> // указатель на последний корень</span>
rollbackEdits.php mass rollback
'''Тонкая куча''Тонкая куча'(англ. ''Thin heap'' ) {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
Тонкие кучи, как и многие другие [[Двоичная куча|кучеобразные]] структуры, аналогичны [[Биномиальная куча|биномиальным кучам]].
{{Определение
|id=thin_tree_def
|definition='''Тонкое дерево''' (англ. ''thin 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=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, и он не имеет детей.
}}
<br clear="all" />
== Тонкая куча ==
{{Определение
|id=thin_forest_def
|definition='''Тонкий лес''' (англ. ''thin Thin forest'') {{---}} это набор тонких деревьев, ранги которых не обязательно попарно различны.
}}
{{Определение
|id=thin_heap_def
|definition='''Тонкая куча''' (англ. ''thin Thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям [[Двоичная куча|кучи]].
}}
|id=max_rank_th
|about=О максимальном ранге узла
|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>T_k</tex> {{---}} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>k</tex>. По свойствам <tex>1</tex> и <tex>3</tex> тонкого дерева получаем следующие соотношения:
<tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_sum\limits_{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 \Phivarphi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> тонкого дерева в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phivarphi}(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 <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>
Также в вершине можно хранить любую дополнительную информацию.
== Операции над тонкой кучей ==
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
{| class="wikitable" style="width:10cm" border=1|+|-align="1center"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>meld\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>\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>
<code>
'''ThinHeap ''' makeHeap(): H.first = ''null'' H.last = ''null '' '''return ''' H;
</code>
<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>
'''Node ''' getMin(H: '''ThinHeap'''): '''return ''' H.first
</code>
Стоимость <tex>O(1)</tex>.
=== meld merge ===
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
<code>
'''ThinHeap meld''' 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>
<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
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>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()
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория: Приоритетные очереди]]
