Изменения

'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} структура данных, отвечающая интерфейсу [[Приоритетные очереди#Операции | приоритетная очередь]]. Эта структура данных имеет меньшую [[Амортизационный анализ#Основные определения | амортизированную сложность]], чем такие приоритетные очереди как [[Биномиальная куча | биномиальная куча]] и [[Двоичная куча | двоичная куча]]. Изначально эта структура данных была разработана Майклом Фридманом<ref>[[wikipedia:en:Michael_Fredman | Майкл Фридман {{---}} Википедия]]</ref> и Робертом Тарьяном<ref>[[wikipedia:en:Robert_Tarjan | Роберт Тарьян {{---}} Википедия]]</ref> при работе по улучшению асимптотической сложности [[Алгоритм Дейкстры | алгоритма Дейкстры]]. Свое название Фибоначчиева куча получила  из-за использования некоторых свойств чисел Фибоначчи<ref>[[wikipedia:en:Fibonacci_number | Числа Фибоначчи {{---}} Википедия]]</ref> в [[Амортизационный анализ#Метод потенциалов | потенциальном анализе]] этой реализации.= Фибоначчиево = Структура ==Фибоначчиева куча {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево =на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одно из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.

'''Фибоначчиево деревоСтепень вершины'''(англ. '' degree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]]количество детей данной вершины. Далее будем обозначать как <tex>degree(x)</tex>, где у каждой вершины удалено не более одного ребенка<tex>x</tex> это вершина.

'''Порядок фибоначчиева дереваСтепень кучи''' (англ. ''degree'') {{---}} порядок соответствующего [[Биномиальная наибольшая степень вершины этой кучи. Далее будем обозначать как <tex>degree(H)</tex>, где <tex>H</tex> это куча#Биномиальное дерево |биномиального дерева]], из которого оно получено.

== Реализация == [[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]Для возможности быстрого удаления элемента из произвольного места и объединением с другим списком будем хранить их в [[Список#Циклический список | циклическом двусвязном списке]]. Также будем хранить и все уровни поддерева. Исходя из этого структура каждого узла будет выглядеть вот так.<code style="display:inline-block"> '''struct''' Node '''int''' key <span style="color:#008000"> // ключ</span> '''Node''' parent <span style="color:#008000"> // указатель на родительский узел</span> '''Node''' child <span style="color:#008000"> // указатель на один из дочерних узлов</span> '''Node''' left <span style="color:#008000"> // указатель на левый узел того же предка</span> '''Node''' right <span style="color:#009000"> // указатель на правый узел того же предка</span> '''int''' degree <span style="color:#008000"> // степень вершины</span> '''boolean''' mark <span style="color:#008000">// был ли удален в процессе изменения ключа ребенок этой вершины)</span></code>Также стоит упомянуть, что нам нужен указатель только на одного ребенка, поскольку остальные хранятся в двусвязном списке с ним. Для доступа ко всей куче нам тоже нужен всего один элемент, поэтому разумно хранить именно указатель на минимум кучи (он обязательно один из корней), а для получения размера за константное время будем хранить размер кучи отдельно.<code style="display:inline-block"> '''struct''' fibonacciHeap '''int''' size <span style="color:#008000">// текущее количество узлов</span> '''Node''' min <span style="color:#008000">// указатель на корень дерева с минимальным ключом</span> </code>==== Cоздание кучи ====Инициализация кучи.<code style="display:inline-block"> '''function''' buildHeap: min <tex>= \varnothing</tex> size = 0</code>==== Вставка элемента ====Данная операция вставляет новый элемент в список корней правее минимума и при необходимости меняет указатель на минимум кучи.<code style="display:inline-block"> '''function''' insert(x: '''int'''): '''Node''' newNode <span style="color:#008000"> // создаем новый узел</span> newNode.key = x <span style="color:#008000"> // инициализируем ключ нового узла</span> '''if''' size = 0 <span style="color:#008000"> // если куче нет элементов, то только что добавленный минимальный</span> min = newNode min.left = newNode min.right = newNode '''else'''<span style="color:#008000"> // иначе аккуратно меняем указатели в списке, чтобы не перепутать указатели</span> '''Node''' prevRight = min.right min.right = newNode newNode.left = min newNode.right = prevRight prevRight.left = newNode '''if''' newNode.key < min.key min = newNode <span style="color:#008000"> // меняем указатель на минимум, если надо</span> newNode.parent <tex>= \varnothing</tex> size++ <span style="color:#008000"> // не забываем увеличить переменную size </span></code>==== Получение минимального элемента ====Получение минимума всей кучи.<code style="display:inline-block"> '''int''' getMin: '''return''' min.key</code>==== Соедининение двух куч ====Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.<code style="display:inline-block"> '''function''' unionLists(first: '''Node''', second: '''Node'''): '''Node''' L = first.left <span style="color:#008000"> // аккуратно меняем указатели местами указатели</span> '''Node''' R = second.right second.right = first first.left = second L.right = R R.left = L</code>Сливаем два корневых списка в один и обновляем минимум, если нужно. <code style="display:inline-block"> '''function''' merge(that: '''fibonacciHeap'''): '''if''' that.size = 0 <span style="color:#008000"> // если вторая куча пуста, нечего добавлять</span> '''return''' '''if''' size = 0 <span style="color:#008000"> // если наша куча пуста, то результатом будет вторая куча</span> min = that.min size = that.size '''else''' unionLists(min, that.min) <span style="color:#008000"> // объединяем два корневых списка</span> size += that.size '''if''' min <tex>= \varnothing</tex> '''or''' (that.min <tex> \neq \varnothing</tex> '''and''' that.min < min) <span style="color:#008000">// если минимум кучи изменился, то надо обновить указатель</span> min = that.min</code> ==== Удаление минимального элемента====Первая рассматриваемая операция, в ходе которой значительно меняется структура кучи. Здесь используется вспомогательная процедура <tex>consolidate</tex>, благодаря которой собственно и достигается желанная амортизированная оценка. В данном случае <tex> min = \varnothing</tex> не рассматривается и считается нарушением предусловий <tex>deleteMin</tex><code style="display:inline-block"> '''int''' deleteMin: '''Node''' prevMin = min unionLists(min, min.child) <span style="color:#008000"> // список детей min объединяем с корневым</span> '''Node''' L = min.left <span style="color:#008000"> // аккуратно удаляем min из списка</span> '''Node''' R = min.right L.right = R R.left = L '''if''' prevMin.right = prevMin <span style="color:#008000"> // отдельно рассмотрим случай с одним элементом</span> min <tex>= \varnothing</tex> '''return''' min = min.right <span style="color:#008000"> // пока что перекинем указатель min на правого сына, а далее consolidate() скорректирует min в процессе выполнения</span> consolidate() size-- '''return''' prevMin.key</code>===== Прорежение деревьев =====Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> degree(H) + 1</tex> вершин. Для этого возьмем массив списков указателей на корни деревьев <tex> A[0 \dots D[H]] </tex>, где <tex> degree(H) </tex> {{Определение---}} максимальная степень вершины в текущем корневом списке. Затем происходит [[Биномиальная_куча#merge |definitionпроцесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку. Подвешиваем мы его следующим образом: в корневой список добавляем корень минимальный из тех двух, а корень другого добавляем в список детей корневой вершины. Чтобы лучше понять этот процесс лучше воспользоваться [https://www.cs.usfca.edu/~galles/visualization/FibonacciHeap.html визуализатором]<code style="display:inline-block"> '''function''' consolidate: A = '''Степень Node[]''' A[min.degree] = min <span style="color:#008000"> // создаем массив и инициализируем его min</span> '''Node''' current = min.right '''while''' A[current.degree] <tex>\neq</tex> current<span style="color:#008000"> // пока элементы массива меняются</span> '''if''' A[current.degree] <tex>= \varnothing</tex> <span style="color:#008000"> // если ячейка пустая, то положим в нее текущий элемент</span> A[current.degree] = current current = current.right '''else''' <span style="color:#008000"> // иначе подвесим к меньшему из текущего корня и того, который лежит в ячейке другой</span> '''Node''' conflict = A[current.degree] '''Node''' addTo, adding '''if''' conflict.key < current.key addTo = conflict adding = current '''else''' addTo = current adding = conflict unionLists(addTo.child, adding) adding.parent = addTo addTo.degree++ current = addTo '''if''' min.key > current.key <span style="color:#008000"> // обновляем минимум, если нужно</span> min = current </code>'''Пример''' Изначально добавляем в нашу кучу <tex>7</tex> элементов <tex>56, 22, 84, 32, 85, 15, 16</tex>. После этого выполним операцию извлечения минимума: [[File:Fibonacci-heap-consolidate-example-1.png|thumb|center|500px|Начальное состояние кучи]]  * Удалим минимальный элемент из циклического корневого списка и заведем массив <tex>A</tex> для дальнейшего прорежения.  [[File:Fibonacci-heap-consolidate-example-2.png|thumb|center|500px|Удаление мимимума и создание массива]]  * Начнем процесс протяжения с первого элемента {{---}} <tex>56</tex>. Его степень равна <tex>0</tex> поэтому запишем его адрес в нулевую ячейку массива.  [[File:Fibonacci-heap-consolidate-example-3.png|thumb|center|500px|Состояние массива после первой итерации]]  * Следующий элемент <tex>22</tex> тоже имеет степень <tex>0</tex>. Возникает конфликт, который решается подвешиванием к меньшему корню большего. То есть к <tex>22</tex> подвешиваем <tex>56</tex> и увеличиваем степень <tex>22</tex> на <tex>1</tex>. В итоге степень <tex>22</tex> равна <tex>1</tex>. Записываем адрес <tex>22</tex> по индексу <tex>1</tex> в массив. [[File:Fibonacci-heap-consolidate-example-4.png.png|thumb|center|500px|Состояние после второй итерации]]  * Делаем тоже самое, что и на предыдущих итерациях, но теперь объединяем <tex>32</tex> и <tex>84</tex>  [[File:Fibonacci-heap-consolidate-example-5.png|thumb|center|500px|Состояние после четвертой итерации]]  * Теперь у нас два элемента со степенью <tex>1</tex> в корневом списке. Объединим их подвесив к меньшему корню {{---}} <tex>22</tex>, больший {{---}} <tex>32</tex>. Теперь степень <tex>22</tex> равна <tex>2</tex>, запишем на <tex>2</tex> позицию массива обновленное значение.  [[File:Fibonacci-heap-consolidate-example-6.png|thumb|center|500px|Состояние после пятой итерации]]   * Ну и наконец аналогично объедений последние два элемента.  [[File:Fibonacci-heap-consolidate-example-7.png|thumb|center|500px|Финальное состояние кучи]] ==== Уменьшение значения элемента ====Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой [[Список |список]]. Итак, сам алгоритм: # Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.# Иначе, вырезаем дерево с текущей вершиной в корневой [[Список |список]], и производим каскадное вырезание родителя. <code style="display:inline-block"> '''function''' decreaseKey(x: '''Node''', newValue: '''int'''): '''if''' newValue > x.parent.key <span style="color:#008000"> // если после изменения структура дерева сохранится, то меняем и выходим</span> x.key = newValue '''return''' '''Node''' parent = x.parent <span style="color:#008000"> // иначе вызываем cut и cascadingCut</span> cut(x) cascadingCut(parent)</code>===== Вырезание =====При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины(<tex> x.mark = false </tex>).<code style="display:inline-block"> ''' function''' cut(x: '''Node''') '''Node''' L = x.left '''Node''' R = x.right R.left = L <span style="color:#008000"> // аккуратно удаляем текущую вершину</span> L.right = R x.parent.degree-- '''if''' x.parent.child = x <span style="color:#008000"> // чтобы родитель не потерял ссылку на сыновей проверяем: </span> '''if''' x.right = x. <span style="color:#008000"> // если узел который мы вырезаем содержится в родителе, то меняем его на соседний</span> x.parent.child <tex>= \varnothing</tex> <span style="color:#008000"> // иначе у родителя больше нет детей</span> '''else''' x.parent.child = x.right x.right = x x.left = x x.parent <tex>= \varnothing</tex> unionLists(min, x) <span style="color:#008000"> // вставляем наше поддерево в корневой список</span></code> ===== Каскадное вырезание =====Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<code style="display:inline-block"> '''function''' cascadingCut(x: '''Node''') '''while''' x.mark = '''true''' <span style="color:#008000"> // пока у нас помеченые вершины вырезаем их</span> cut(x) x = x.parent x.mark = true <span style="color:#008000"> // последнюю вершину нужно пометить {{---}} порядок фибоначчиева у нее удаляли ребенка</span></code> '''Пример''' Рисунок иллюстрирует пример каскадного вырезания: * Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, чьим корнем эта вершина являетсяпоэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой [[Список |список]] и помечаем ее родителя.* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев. ==== Удаление элемента ====Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума.<code style="display:inline-block"> '''function''' delete(x: '''Node''') decreaseKey(x, <tex>-\infty</tex>) deleteMin()</code>

Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.

Но по предыдущей [[#Лемма1|лемме]] <tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex>}} = Фибоначчиева куча =:

<tex>1 + \sum\limits_{{Определение|definitioni='''Фибоначчиева куча''' {0}^{n---2}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]F_i = F_n</tex>. В отличие от [[Биномиальная куча|биномиальной кучи]]Следовательно, степени корней не обязаны быть попарно различными.<tex>s_n \geqslant F_n</tex>

|statement= <tex>F_n =\ThetaO(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex>

Поскольку <tex>\left\vert (-\varphi)^{-1} \right\vert < 1</tex>, то выполняются неравенства <tex dpi="160">\frac {(-\varphi)^{-n}} {\sqrt 5} < \frac {1} {\sqrt 5} < \frac {1} {2}</tex>. Таким образом, <tex>n</tex>-ое число Фибоначчи равно <tex dpi="160">\frac {\varphi^{n}} {\sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_n =\ThetaO(\varphi^n)</tex>.

|statement=Максимальная степень <tex>D(n)degree</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log(n))</tex>

Пусть <tex>x</tex> {{---}} произвольная вершина в фибоначчиевой куче с <tex>n</tex> вершинами, и пусть <tex>k</tex> {{---}} степень вершины <tex>x</tex>. Тогда по [[#Лемма2|доказанному выше]] в дереве, корень которого <tex>x</tex>, содержится не менее <tex>F_k</tex> вершин, что в свою очередь по [[#Лемма3|лемме]] равно <tex>\ThetaO(\varphi^k)</tex>.

Таким образом, максимальная степень <tex>D(n)degree</tex> произвольной вершины равна <tex>O(\log(n))</tex>.

== Структура ==[[File:Fibonacci-heap.png|thumb|350px|Пример фибоначчиевой кучи]]* Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:** <tex>x.key</tex> — поле, в котором хранится ключ;** <tex>x.p</tex> — указатель на родительский узел;** <tex>x.child</tex> — указатель на один из дочерних узлов;** <tex>x.left</tex> — указатель на левый сестринский узел;** <tex>x.right</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>. [[Список#Циклический список | Циклический]] [[Список#Двусвязный список | двусвязный список]] обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>. == Потенциал == Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты. == Операции ==Рассмотрим Итоговая асимптотика операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.{| border="1" |-align="center" |<tex>makeHeap</tex> |<tex>O(1)</tex> |-align="center" |<tex>insert</tex> |<tex>O(1)</tex> |-align="center" |<tex>getMin</tex> |<tex>O(1)</tex> |-align="center" |<tex>merge</tex> |<tex>O(1)</tex> |-align="center" |<tex>extractMin</tex> |<tex>O(\log(n))</tex> |-align="center" |<tex>decreaseKey</tex> |<tex>O(1)</tex> |-align="center" |<tex>delete</tex> |<tex>O(\log(n))</tex> |}Стоит заметить, что структура фибоначчиевых куч, также как [[Биномиальная куча|биномиальных]] и [[Двоичная куча|бинарных]], не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>decreaseKey</tex> и <tex>delete</tex> получают в качестве аргумента указатель на узел, а не значение его ключа. === makeHeap === Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы mathrm {{---}extraxtMin} <tex> O(1) </tex>. === insert === Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4 = <tex> O(1) </tex>. === getMin ===Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex> === merge === Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>. === extractMin === Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> consolidate </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> consolidate </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>extraxtMin</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate } </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n)degree)+O(D(n)degree)=O(D(n)degree) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)degree) = O(\log(n))</tex>. ==== consolidate ==== Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин. Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке. Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку. Учетная стоимость <tex> consolidate </tex> равна <tex> O(D(n)) </tex>. Докажем это: Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> consolidate </tex> мы сделали <tex> O(D(n) + t[H]) </tex> слияний деревьев. Потенциал перед извлечением минимума равен <tex> t[H] + 2m[H] </tex>, а после не превышает <tex> D(n) + 1 + 2m[H] </tex>, поскольку в корневом списке остается не более <tex> D(n) + 1 </tex> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит <tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex> Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex> === decreaseKey === Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм: # Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.  ==== cut ==== При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>). ==== cascadingCut ==== [[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]] Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>cut</tex> для текущей вершины и запускаем каскадное вырезание от родителя. '''Пример''' Рисунок иллюстрирует пример каскадного вырезания: * Изначально, куча состояла из 3 фибоначчиевых деревьев. У вершины с ключом 24 отсутствует 1 ребенок.* Уменьшаем ключ 26 до 5 и делаем операцию <tex>cut</tex> этого дерева. Получаем кучу с 4 деревьями и новым минимумом. Но у вершины с ключом 24 был удален второй ребенок, поэтому запускам операцию <tex>cascadingCut</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.* У вершины с ключом 7 удален лишь один ребенок, поэтому операция <tex>cascadingCut</tex> от нее не запускается. В итоге, получаем кучу, состоящую из 5 фибоначчиевых деревьев.

ДокажемИзначально в корневом списке было не более <tex> degree + trees - 1 </tex> вершин, что амортизированное время работы поскольку он состоит из исходного списка корней с <tex>trees</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> degree </tex>. В ходе операции <tex>decreaseKey\mathrm {consolidate} </tex> есть мы сделали <tex> O(1degree + trees) </tex>слияний деревьев. Поскольку Потенциал перед извлечением минимума равен <tex> trees + 2 * marked </tex>, а после не превышает <tex> degree + 1 + 2 * marked</tex>, поскольку в процедуре нет цикловкорневом списке остается не более <tex> degree + 1 </tex> узлов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезанияа количество помеченных узлов не изменяется.Таким образом, амортизированная стоимость не превосходит

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> x.mark = true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(kdegree + trees) + \Phi_i - \Phi_{i - (degree + 1} = O(k+ 2 * marked) + - (k - 2k trees + 2 * marked) = O(1degree)) </tex>. Следовательно, амортизированная стоимость не превышает <tex> + O(1trees) - trees</tex>, поскольку мы можем соответствующим образом масштабировать единицы потенциала.

На языке метода предоплаты: пусть у каждого узла в списке корней лежит монетаПоскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, а у каждой помеченной вершины то итоговая амортизационная оценка {{---}} 2 монеты. Покажем, что взяв 4 монеты за операцию <tex> decreaseKey O(degree) </tex>==== Уменьшение значения элемента ====Докажем, мы сможем оплатить эту операцию. Одну монету потратим на перенос в корневой список и релаксацию минимума, еще 1 {{---}} на то, чтобы положить монету у новой вершины в корневом списке, которую мы потратим на следующую операцию что амортизированное время работы операции <tex>extractMin\mathrm {decreaseKey} </tex>. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда есть <tex> x.p.mark = false O(1) </tex>. Поскольку в процедуре нет циклов, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняетсяее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Иначе, добавляем к помеченной вершине родителя еще 2 монетыПусть мы вызвали процедуру каскадного вырезания подверглось <tex> k </tex> раз. В итогеТак как реальное время работы каждой итерации <tex> \mathrm {cascadingCut} </tex> составляет <tex> O(1) </tex>, в родительском узле становится 4 монеты, и мы можем рекурсивно продолжить данный процесс. Оценка доказанато реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>.

Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> итераций операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark === delete ===true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>).

Удаление вершины реализуется через уменьшение ее ключа до В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((trees + k) + 2 * (marked + k - 2)) - (trees + 2 * marked) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 -k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \infty mathrm {decreaseKey} </tex> равна <tex> O(1) </tex> и последующим извлечением минимума. ==== Удаление элемента ====Амортизированное время работы: <tex> O(1) + O(D(n)degree) = O(D(n)degree) </tex>.

Поскольку ранее мы показали, что <tex> D(n) degree = O(\log(n)) </tex>, то соответствующие оценки доказаны.==== Итоговая таблица ===={| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Операция!style="background-color:#EEE"| Амортизированная сложность|-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> |}

= Источники =Недостатки и достоинства =='''Недостатки''':* Большое потребление памяти на узел(минимум 21 байт)* Большая константа времени работы, что делает ее малоприменимой для реальных задач* Некоторые операции в худшем случае могут работать за <tex>O(n)</tex> времени'''Достоинства''':* Одно из лучших асимптотических времен работы для всех операций

* [http[wikipedia:en://ru.wikipedia.org/wiki/Числа_Фибоначчи Числа Фибоначчи — |Числа Фибоначчи {{---}} Википедия]]* [[wikipedia:en:Fibonacci heap|Фибоначчиева куча {{---}} Википедия]]* [httphttps://ruwww.cs.wikipediausfca.orgedu/~galles/wikivisualization/Фибоначчиева_куча Фибоначчиева куча — ВикипедияFibonacciHeap.html Fibonacci heap visualization]

* [http://rainwww.cs.ifmoduke.ruedu/catcourses/view.phpfall05/viscps230/heaps ВизуализаторыL-11.pdf Fibonacci Heaps {{---}} Duke University]* [httphttps://www.cs.dukeprinceton.edu/courses/fall05~wayne/cps230teaching/Lfibonacci-11heap.pdf Fibonacci Heaps{{---}} Princeton University]

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]