27
правок
Изменения
Нет описания правки
|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 \Phi^{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 \Phi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
<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>
<code>
'''ThinHeap''' meld(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()
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория: Приоритетные очереди]]
