1632
правки
Изменения
м
rollbackEdits.php mass rollback
<br clear="all" />
== Тонкая куча ==
{{Определение
|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>.
}}
||<tex>\mathrm{getMin}</tex>||<tex>O(1)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm{meldmerge}</tex>||<tex>O(1)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm{extractMin}</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>
'''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
<code>
'''Node''' getMin(H: '''ThinHeap'''):
'''return''' H.first
</code>
Стоимость <tex>O(1)</tex>.
=== meld merge ===
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
<code>
'''ThinHeap''' meldmerge(H1: '''ThinHeap''', H2: '''ThinHeap'''): '''if''' H1.first == ''null''
'''return''' H2
'''else'''
'''if''' H2.first == ''null''
'''return''' H1
'''else'''
<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)
max = -1
x = H.first
'''while''' x != ''null'' '''while''' aux[x.rank] != ''null''
next = x.right
'''if''' aux[x.rank].key < x.key
aux[x.rank].left = x
x.child = aux[x.rank]
aux[x.rank] = ''null ''
x.rank = x.rank + 1
aux[x.rank] = x
<code>
'''void''' delete(H: '''ThinHeap''', x: '''Node'''):
decreaseKey(H, x, <tex>-\infty</tex>)
extractMin()
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория: Приоритетные очереди]]
