42
правки
Изменения
Нет описания правки
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}
[[File:Fibonacci-heap.png|thumb|273px|Пример фибоначчиевой кучи]]
Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.
=== Каскадное вырезание ===
[[File:Cascading-cut.png|thumb|273px|Каскадное вырезание]]
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.
Иначе, <tex> mark[p[x]] == true </tex> и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.
На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с <tex> mark[x] == true </tex>.
== Удаление вершины ==
* http://www.intuit.ru/department/algorithms/dscm/7/2.html - INTUIT.ru
* Визуализаторы на rain.ifmo.ru: http://rain.ifmo.ru/cat/view.php/vis/heaps
* http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf
