3622
правки
Изменения
м
→Тонкая куча
<br clear="all" />
== Тонкая куча ==
{{Определение
|about=О максимальном ранге узла
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex>\varphi=\dfrac{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\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>.
}}
