Изменения

{{Определение

|definition=

}}

{{Определение

}}

[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]

* Каждый узел <tex>x</tex> в куче <tex>H</tex> содержит следующие указатели и поля:

Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.

Для анализа производительности операций введем потенциал для фибоначчиевой кучи <tex>H</tex> как <tex> \Phi(H) = t[H] + 2m[H] </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.

Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.

{| border="1"

Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.

Создается новый пустой корневой список, в <tex> H.min </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Для оценки амортизированной стоимости операции рассмотрим исходную кучу <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>.

Возвращает указатель <tex>H.min</tex>. Реальное время работы {{---}} <tex> O(1) </tex>.

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <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>.

Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> D(n) + 1</tex> вершин.

Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(D(n)) </tex>

Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:

# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).

[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]

* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.

Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </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>.

Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D(n)) = O(D(n)) </tex>.

Поскольку ранее мы показали, что <tex> D(n) = O(\log n ) </tex>, то соответствующие оценки доказаны.

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4