Изменения

== Фибоначчиева куча ==

{{Определение

|definition=

'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.

}}

Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.

=== Структура ===

====Структура узла====

Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:

'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span>

====Структура списка детей====

* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список.

* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список корней.