403
правки
Изменения
→Фибоначчиевы кучи
{{Лемма
|id=лемма4
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log(n))</tex>
|proof=
Пусть <tex>x</tex> {{---}} произвольная вершина в фибоначчиевой куче с <tex>n</tex> вершинами, и пусть <tex>k</tex> {{---}} степень вершины <tex>x</tex>. Тогда по [[#Лемма2|доказанному выше]] в дереве, корень которого <tex>x</tex>, содержится не менее <tex>F_k</tex> вершин, что в свою очередь по [[#Лемма3|лемме]] равно <tex>\Theta(\varphi^k)</tex>.
Логарифмируя по основанию <tex>\varphi</tex>, получаем
<tex>\log_{\varphi}n \geqslant k</tex>
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log(n))</tex>.
}}
|-align="center"
|<tex>makeHeap</tex>
|<tex>\ThetaO(1)</tex>
|-align="center"
|<tex>insert</tex>
|<tex>\ThetaO(1)</tex>
|-align="center"
|<tex>getMin</tex>
|<tex>\ThetaO(1)</tex>
|-align="center"
|<tex>merge</tex>
|<tex>\ThetaO(1)</tex>
|-align="center"
|<tex>extractMin</tex>
|-align="center"
|<tex>decreaseKey</tex>
|<tex>\ThetaO(1)</tex>
|-align="center"
|<tex>delete</tex>
