77
правок
Изменения
Нет описания правки
|proof=
Докажем это утверждение по индукции.
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.
При <tex>n = 0</tex>
Фибоначчиевы кучи поддерживают тот же набор операций, что и [[Биномиальная куча|биномиальные кучи]], но имеют то преимущество, что операции, в которых не требуется удаление, имеют [[Амортизационный анализ|амортизированное]] время работы, равное <tex>O(1)</tex>.
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>\mathrm {extractMin}</tex> и <tex>\mathrm {delete}</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные [[Двоичная куча|бинарные кучи]].
{{Лемма
{{Лемма
|id=Лемма4
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log(n))</tex>
|proof=
Пусть <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>.
<tex>\log_{\varphi}n \geqslant k</tex>
Таким образом, максимальная степень <tex>D(n)</tex> произвольной вершины равна <tex>O(\log(n))</tex>.
}}
|-align="center"
|<tex>extractMin</tex>
|<tex>O(\log(n))</tex>
|-align="center"
|<tex>decreaseKey</tex>
|-align="center"
|<tex>delete</tex>
|<tex>O(\log(n))</tex>
|}
Стоит заметить, что структура фибоначчиевых куч, также как [[Биномиальная куча|биномиальных]] и [[Двоичная куча|бинарных]], не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.
=== makeHeap ===
=== extractMin ===
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <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>.
==== consolidate ====
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.
Учетная стоимость <tex> \mathrm {consolidate } </tex> равна <tex> O(D(n)) </tex>. Докажем это:
Изначально в корневом списке было не более <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> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит
<tex> O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H]</tex>
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.
'''Пример'''
Рисунок иллюстрирует пример каскадного вырезания:
* Изначально, куча состояла из <tex>3 </tex> фибоначчиевых деревьев. У вершины с ключом <tex>24 </tex> отсутствует <tex>1 </tex> ребенок.* Уменьшаем ключ <tex>26 </tex> до <tex>5 </tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4 </tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24 </tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.* У вершины с ключом <tex>7 </tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5 </tex> фибоначчиевых деревьев.
==== Время работы ====
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey } </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Так как реальное время работы операции <tex> \mathrm {cascadingCut } </tex> без учета рекурсии составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey } </tex> {{---}} <tex> O(k) </tex>.
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey } </tex>. Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> \mathrm {cascadingCut } </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut } </tex>).
В итоге, изменение потенциала составляет: <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>.
=== delete ===
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.
Поскольку ранее мы показали, что <tex> D(n) = O(\log(n)) </tex>, то соответствующие оценки доказаны.
= Источники =
