77
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Порядок фибоначчиева дерева''' {{---}} порядок соответствующего [[Биномиальная куча#Биномиальное дерево |биномиального дерева]], из которого оно получено.
}}
}}
Фибоначчиевы кучи поддерживают тот же набор операций, что и [[Биномиальная куча|биномиальные кучи]], но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].
** <tex>x.degree</tex> — поле, в котором хранится количество дочерних узлов;
** <tex>x.mark</tex> — логическое значение, которое показывает, удаляли ли мы дочерние узлы данной вершины.
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]].* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]] корней.
* Обращение к <tex>H</tex> выполняется посредством указателя <tex>H.min</tex> на корень дерева с минимальным ключом. Этот узел называется минимальным узлом <tex>H</tex>.
* Текущее количество узлов в <tex>H</tex> хранится в <tex>H.size</tex>.
== Потенциал ==
{| border="1"
|-align="center"
|<tex>\mathrm {makeHeap}</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>\mathrm {insert}</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>\mathrm {getMin}</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>\mathrm {merge}</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>\mathrm {extractMin}</tex>
|<tex>O(\log n )</tex>
|-align="center"
|<tex>\mathrm {decreaseKey}</tex>
|<tex>O(1)</tex>
|-align="center"
|<tex>\mathrm {delete}</tex>
|<tex>O(\log n )</tex>
|}
Стоит заметить, что структура фибоначчиевых куч, также как [[Биномиальная куча|биномиальных]] и [[Двоичная куча|бинарных]], не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.
=== makeHeap ===
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.
= Источники информации =
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
