http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=217.66.156.128&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T01:36:33ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46767Фибоначчиева куча2015-05-21T16:01:18Z<p>217.66.156.128: /* cascadingCut */</p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree rank'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000"> // ключ</span><br />
'''Node''' p <span style="color:#008000"> // указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000"> // указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000"> // указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000"> // указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000"> // количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
<br />
====Структура кучи====<br />
'''struct''' Heap<br />
'''int''' size <span style="color:#008000">// текущее количество узлов</span><br />
'''Node''' min <span style="color:#008000">// указатель на корень дерева с минимальным ключом</span><br />
====Структура списка детей====<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]].<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]] корней.<br />
<br />
[[Список#Циклический список |Циклический]] [[Список#Двусвязный список | двусвязный список]] обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой [[Список#Двусвязный список | список]], в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой [[Список |список]]. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой [[Список |список]], и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой [[Список |список]] и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
==См. также==<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46766Фибоначчиева куча2015-05-21T16:00:46Z<p>217.66.156.128: /* decreaseKey */</p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree rank'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000"> // ключ</span><br />
'''Node''' p <span style="color:#008000"> // указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000"> // указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000"> // указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000"> // указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000"> // количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
<br />
====Структура кучи====<br />
'''struct''' Heap<br />
'''int''' size <span style="color:#008000">// текущее количество узлов</span><br />
'''Node''' min <span style="color:#008000">// указатель на корень дерева с минимальным ключом</span><br />
====Структура списка детей====<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]].<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]] корней.<br />
<br />
[[Список#Циклический список |Циклический]] [[Список#Двусвязный список | двусвязный список]] обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой [[Список#Двусвязный список | список]], в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой [[Список |список]]. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой [[Список |список]], и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
==См. также==<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46765Фибоначчиева куча2015-05-21T15:59:44Z<p>217.66.156.128: /* makeHeap */</p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree rank'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000"> // ключ</span><br />
'''Node''' p <span style="color:#008000"> // указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000"> // указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000"> // указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000"> // указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000"> // количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
<br />
====Структура кучи====<br />
'''struct''' Heap<br />
'''int''' size <span style="color:#008000">// текущее количество узлов</span><br />
'''Node''' min <span style="color:#008000">// указатель на корень дерева с минимальным ключом</span><br />
====Структура списка детей====<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]].<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]] корней.<br />
<br />
[[Список#Циклический список |Циклический]] [[Список#Двусвязный список | двусвязный список]] обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой [[Список#Двусвязный список | список]], в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
==См. также==<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46764Фибоначчиева куча2015-05-21T15:58:45Z<p>217.66.156.128: /* Структура списка детей */</p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree rank'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000"> // ключ</span><br />
'''Node''' p <span style="color:#008000"> // указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000"> // указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000"> // указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000"> // указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000"> // количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
<br />
====Структура кучи====<br />
'''struct''' Heap<br />
'''int''' size <span style="color:#008000">// текущее количество узлов</span><br />
'''Node''' min <span style="color:#008000">// указатель на корень дерева с минимальным ключом</span><br />
====Структура списка детей====<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]].<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]] корней.<br />
<br />
[[Список#Циклический список |Циклический]] [[Список#Двусвязный список | двусвязный список]] обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
==См. также==<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46763Фибоначчиева куча2015-05-21T15:54:52Z<p>217.66.156.128: /* Структура узла */</p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree rank'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000"> // ключ</span><br />
'''Node''' p <span style="color:#008000"> // указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000"> // указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000"> // указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000"> // указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000"> // количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
<br />
====Структура кучи====<br />
'''struct''' Heap<br />
'''int''' size <span style="color:#008000">// текущее количество узлов</span><br />
'''Node''' min <span style="color:#008000">// указатель на корень дерева с минимальным ключом</span><br />
====Структура списка детей====<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список.<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список корней.<br />
<br />
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
==См. также==<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46735Фибоначчиева куча2015-05-20T17:55:50Z<p>217.66.156.128: </p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree order'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000">// ключ</span><br />
'''Node''' p <span style="color:#008000">// указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000">// указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000">// указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000">// указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000">// количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
====Структура списка детей====<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список.<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список корней.<br />
* Обращение к <tex>H</tex> выполняется посредством указателя <tex>H.min</tex> на корень дерева с минимальным ключом. Этот узел называется минимальным узлом <tex>H</tex>.<br />
* Текущее количество узлов в <tex>H</tex> хранится в <tex>H.size</tex>.<br />
<br />
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
==См. также==<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46734Фибоначчиева куча2015-05-20T17:43:06Z<p>217.66.156.128: </p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree order'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000">// ключ</span><br />
'''Node''' p <span style="color:#008000">// указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000">// указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000">// указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000">// указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000">// количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
====Структура списка детей====<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список.<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список корней.<br />
* Обращение к <tex>H</tex> выполняется посредством указателя <tex>H.min</tex> на корень дерева с минимальным ключом. Этот узел называется минимальным узлом <tex>H</tex>.<br />
* Текущее количество узлов в <tex>H</tex> хранится в <tex>H.size</tex>.<br />
<br />
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
==См. также==<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46733Фибоначчиева куча2015-05-20T17:37:40Z<p>217.66.156.128: </p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree order'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
====Структура узла====<br />
Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000">// ключ</span><br />
'''Node''' p <span style="color:#008000">// указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000">// указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000">// указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000">// указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000">// количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
====Структура списка детей====<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список.<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список корней.<br />
* Обращение к <tex>H</tex> выполняется посредством указателя <tex>H.min</tex> на корень дерева с минимальным ключом. Этот узел называется минимальным узлом <tex>H</tex>.<br />
* Текущее количество узлов в <tex>H</tex> хранится в <tex>H.size</tex>.<br />
<br />
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46732Фибоначчиева куча2015-05-20T17:28:15Z<p>217.66.156.128: </p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree order'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''struct''' Node<br />
'''int''' key <span style="color:#008000">// ключ</span><br />
'''Node''' p <span style="color:#008000">// указатель на родительский узел</span><br />
'''Node''' child <span style="color:#008000">// указатель на один из дочерних узлов</span><br />
'''Node''' left <span style="color:#008000">// указатель на левый сестринский узел</span><br />
'''Node''' right <span style="color:#008000">// указатель на правый сестринский узел</span><br />
'''int''' degree <span style="color:#008000">// количество дочерних узлов</span><br />
'''boolean''' mark <span style="color:#008000">// флаг, который показывает, удаляли ли мы дочерние узлы данной вершины</span><br />
<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список.<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список корней.<br />
* Обращение к <tex>H</tex> выполняется посредством указателя <tex>H.min</tex> на корень дерева с минимальным ключом. Этот узел называется минимальным узлом <tex>H</tex>.<br />
* Текущее количество узлов в <tex>H</tex> хранится в <tex>H.size</tex>.<br />
<br />
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0&diff=46731Фибоначчиева куча2015-05-20T17:19:53Z<p>217.66.156.128: </p>
<hr />
<div>== Фибоначчиево дерево ==<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиево дерево''' (англ. ''Fibonacci tree'') {{---}} [[Биномиальная куча#Биномиальное дерево |биномиальное дерево]], где у каждой вершины удалено не более одного ребенка.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Порядок фибоначчиева дерева''' (англ. ''Fibonacci tree order'') {{---}} порядок соответствующего биномиального дерева, из которого оно получено.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Степень вершины''' (англ. ''degree'') {{---}} количество дочерних узлов данной вершины.<br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма1<br />
|statement=Для всех целых <tex> n \geqslant 2</tex><br />
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,<br />
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:<br />
<tex><br />
F_n =<br />
\begin{cases}<br />
0, & n = 0 \\<br />
1, & n = 1 \\<br />
F_{n-1} + F_{n-2}, & n \geqslant 2<br />
\end{cases} </tex><br />
|proof=<br />
Докажем лемму по индукции:<br />
<br />
при <tex>n = 2</tex><br />
<br />
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
}}<br />
<br />
{{Лемма<br />
|id=Лемма2<br />
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.<br />
|proof=<br />
Докажем это утверждение по индукции.<br />
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>s_0 = 1 > F_0</tex>.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>s_1 = 1 = F_1</tex>.<br />
<br />
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.<br />
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда<br />
<br />
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex><br />
<br />
Но по предыдущей [[#Лемма1|лемме]] :<br />
<br />
<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex><br />
}}<br />
<br />
== Фибоначчиева куча ==<br />
<br />
{{Определение<br />
|definition=<br />
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный [[Список#Циклический список |циклический]] [[Список#Двусвязный список | двусвязный список]]. В отличие от [[Биномиальная куча|биномиальной кучи]], степени корней не обязаны быть попарно различными.<br />
}}<br />
<br />
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.<br />
<br />
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].<br />
<br />
{{Лемма<br />
|id=Лемма3<br />
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex><br />
|proof=<br />
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex><br />
<br />
Используем для этого математическую индукцию.<br />
<br />
При <tex>n = 0</tex><br />
<br />
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.<br />
<br />
При <tex>n = 1</tex><br />
<br />
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.<br />
<br />
По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда<br />
<br />
<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex><br />
<br />
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex><br />
<br />
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex><br />
<br />
Поскольку <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 =\Theta(\varphi^n)</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=Лемма4<br />
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex><br />
|proof=<br />
Пусть <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>.<br />
То есть<br />
<br />
<tex>n \geqslant \varphi^{k}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant k</tex><br />
<br />
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log n)</tex>.<br />
}}<br />
<br />
=== Структура ===<br />
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]<br />
* Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:<br />
'''Node'''<br />
int key; //ключ<br />
Node* p; //указатель на родительский узел<br />
Node* child; //указатель на один из дочерних узлов<br />
Node* left; //указатель на левый сестринский узел<br />
Node* right; //указатель на правый сестринский узел<br />
int degree; //количество дочерних узлов<br />
boolean mark; //флаг, который показывает, удаляли ли мы дочерние узлы данной вершины<br />
<br />
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список.<br />
* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в циклический двусвязный список корней.<br />
* Обращение к <tex>H</tex> выполняется посредством указателя <tex>H.min</tex> на корень дерева с минимальным ключом. Этот узел называется минимальным узлом <tex>H</tex>.<br />
* Текущее количество узлов в <tex>H</tex> хранится в <tex>H.size</tex>.<br />
<br />
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.<br />
<br />
=== Потенциал ===<br />
<br />
Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.<br />
<br />
=== Операции ===<br />
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Операция<br />
!style="background-color:#EEE"| Амортизированная сложность<br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> <br />
|-align="center"<br />
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex><br />
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> <br />
|}<br />
<br />
<br />
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.<br />
<br />
==== makeHeap ====<br />
<br />
Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== insert ====<br />
<br />
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (t[H] + 1 + 2m[H]) - (t[H] + 2m[H]) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.<br />
<br />
==== getMin ====<br />
Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.<br />
<br />
==== merge ====<br />
<br />
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.<br />
<br />
==== extractMin ====<br />
<br />
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> \mathrm {consolidate} </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> \mathrm {consolidate} </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(D(n)) = O(\log(n))</tex>.<br />
<br />
===== consolidate =====<br />
<br />
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.<br />
<br />
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.<br />
<br />
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.<br />
<br />
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(D(n)) </tex>. Докажем это:<br />
<br />
Изначально в корневом списке было не более <tex> D(n) + t[H] - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>t[H]</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> D(n) </tex>. В ходе операции <tex> \mathrm {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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит<br />
<br />
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex><br />
<br />
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex><br />
<br />
==== decreaseKey ====<br />
<br />
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:<br />
<br />
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.<br />
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. <br />
<br />
===== cut =====<br />
<br />
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).<br />
<br />
===== cascadingCut =====<br />
<br />
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]<br />
<br />
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.<br />
<br />
'''Пример'''<br />
<br />
Рисунок иллюстрирует пример каскадного вырезания:<br />
<br />
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.<br />
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.<br />
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.<br />
<br />
===== Время работы =====<br />
<br />
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.<br />
<br />
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut} </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>. <br />
<br />
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>). <br />
<br />
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.<br />
<br />
==== delete ====<br />
<br />
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.<br />
<br />
Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.<br />
<br />
== Источники информации ==<br />
<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4<br />
* [[wikipedia:ru:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]<br />
* [[wikipedia:ru:Фибоначчиева куча|Фибоначчиева куча {{---}} Википедия]]<br />
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/heaps Визуализаторы]<br />
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>217.66.156.128