1632
правки
Изменения
м
|statement= <tex>F_n =\Theta(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex>
|proof=
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex>
Используем для этого математическую индукцию.
При <tex>n = 0</tex>
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.
При <tex>k = 1</tex>
<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>, что также верно.
По индукции предполагаем, что <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>. Тогда
<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>
<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>
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex>
Поскольку <tex>\left\vert (-\varphi)^{-1} \right\vert < 1</tex>, то выполняются неравенства <tex dpi="160">\frac {(-\varphi)^{-n}} {\sqrt 5} < \frac {1} {\sqrt 5} < \frac {1} {2}</tex>. Таким образом, <tex>n</tex>-е число Фибоначчи равно <tex dpi="160">\frac {\varphi^{n}} {\sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_n =\Theta(\varphi^n)</tex>.
}}
{{Лемма
|id=Лемма3
[[File:Fibonacci-heapИспользуем для этого математическую индукцию.png|thumb|300px|Пример фибоначчиевой кучи]]
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное При <tex>O(1)n = 0</tex>.
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций <tex>ExtractMinF_0 =</tex> и <texdpi="160">Delete\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex> относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные бинарные кучичто верно.
Введем потенциал фибоначчиевой кучи По индукции предполагаем, что <tex> \Phi(H) F_{n-1} = C(t[H] + 2m[H]) </tex>, где <texdpi="160"> t[H] </tex> \frac {\varphi^{n-1} - (-\varphi)^{1-n}}{\sqrt 5} количество элементов в корневом списке кучи, а </tex> m[H] и </tex> F_{{--n-2}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> mark[x] == true </tex>). Подходящую константу <texdpi="160"> C \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.Тогда
Создается новый пустой корневой список, в <texdpi="160"> min[H] = \frac {1} {\sqrt 5}</tex> устанавливается значение <tex> null (\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex>. Реальное время работы <tex dpi="160">= \frac {1} {---}\sqrt 5} </tex> <tex> O(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2})) </tex>.
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в одинПоскольку <tex>\left\vert (-\varphi)^{-1} \right\vert < 1</tex>, релаксируем минимум. Реальное время работы то выполняются неравенства <tex dpi="160">\frac {(-\varphi)^{---n}} {\sqrt 5} < \frac {1}{\sqrt 5} <tex> O(\frac {1) } {2}</tex>. Амортизированное время работы - также Таким образом, <tex> O(1) n</tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, -ое число Фибоначчи равно <texdpi="160"> \Phi_frac {\varphi^{n + 1} - } {\Phi_n sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_n = 0 O(\varphi^n)</tex>.}}
== Вставка элемента ==
Вставка элемента {{Лемма|id=Лемма4|statement=Максимальная степень <tex>degree</tex> произвольной вершины в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается фибоначчиевой куче с текущей. Амортизированная стоимость операции: 1 <tex>n</tex> вершинами равна <tex>O(создание кучи\log n) + 2 </tex>|proof=Пусть <tex>x</tex> {{---}} произвольная вершина в фибоначчиевой куче с <tex>n</tex> вершинами, и пусть <tex>k</tex> {{---}} степень вершины <tex>x</tex>. Тогда по [[#Лемма2|доказанному выше]] в дереве, корень которого <tex>x</tex>, содержится не менее <tex>F_k</tex> вершин, что в свою очередь по [[#Лемма3|лемме]] равно <tex>O(слияние куч + релаксация минимума\varphi^k) + 1(изменение потенциала) = 4</tex>.То есть
== Извлечение минимума ==<tex>n \geqslant \varphi^{k}</tex>
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем Логарифмируя по основанию <tex> D[H] \varphi</tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.получаем
=== "Уплотнение" (Consolidate) ===<tex>\log_{\varphi}n \geqslant k</tex>
Данная процедура принимает кучуТаким образом, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин. Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>. Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d degree</tex>. Если в соответствующей ячейке A еще нету произвольной вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку. Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]\log n) </tex>. Докажем это: Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>. На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это <tex> O(D[H]) </tex> действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру <tex> Consolidate </tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого <tex> O(D[H]) + O(D[H]) = O(D[H]) </tex> действий. == Уменьшение ключа == Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня; тогда дерево не придется сильно перестраивать. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм: # Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя. === Вырезание вершины === При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> degree[p[x]] </tex>) и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>). === Каскадное вырезание ===}
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если Учетная стоимость <tex> mark[x] == false \mathrm {consolidate} </tex>, то мы ставим эту пометку равна <tex> true O(degree) </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.Докажем это:
ДокажемИзначально в корневом списке было не более <tex> degree + trees - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>trees</tex> узлами, минус извлеченный узел и плюс дочерние узлы, что амортизированное время работы количество которых не превышает <tex> degree </tex>. В ходе операции "уменьшение ключа" есть <tex> \mathrm {consolidate} </tex> мы сделали <tex> O(1degree + trees) </tex>слияний деревьев. Поскольку Потенциал перед извлечением минимума равен <tex> trees + 2 * marked </tex>, а после не превышает <tex> degree + 1 + 2 * marked</tex>, поскольку в процедуре нет цикловкорневом списке остается не более <tex> degree + 1 </tex> узлов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезанияа количество помеченных узлов не изменяется.Таким образом, амортизированная стоимость не превосходит
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(kdegree + trees) + \Phi_i - \Phi_{i - (degree + 1} = O(k+ 2 * marked) + C- (k - 2k trees + 2 * marked) = O(1degree)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> + O(1trees) - trees</tex>. Теперь также стало ясно, для чего в определении нашего потенциала количество вершин с пометкой <tex> mark[x] </tex> учитывается вдвое больше, чем количество вершин в корневом списке.
На языке метода предоплаты: ПокажемПоскольку мы договорились, что взяв в начале 4 монетыможем масштабировать единицу потенциала таким образом, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимумачтобы покрывать константное количество работы, еще 1 то итоговая амортизационная оценка {{--- на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда }} <tex> O(degree) </tex> mark[p[x]] == false == Уменьшение значения элемента ====Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex>есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняетсяее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
Иначе, Пусть мы вызвали процедуру каскадного вырезания подверглось <tex> mark[p[x]] == true k </tex> и там лежит 2 монетыраз. 2 + 2 = 4Так как реальное время работы каждой итерации <tex> \mathrm {cascadingCut} </tex> составляет <tex> O(1) </tex>, и мы можем рекурсивно продолжить данный процесс. Оценка доказанато реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>.
На рисунке проиллюстрирован процесс понижения ключа вершины c 10 Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до 7вызова <tex> \mathrm {decreaseKey} </tex>. Серым помечены вершины Тогда после <tex> k </tex> итераций операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark[x] == true </tex>стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>).
Удаление вершины реализуется через уменьшение ее ключа до Поскольку ранее мы показали, что <tex> degree = O(\log n ) </tex>, то соответствующие оценки доказаны.==== Итоговая таблица ===={| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Операция!style="background-color:#EEE"| Амортизированная сложность|-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\infty mathrm {makeHeap}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> и последующим извлечением минимума. Амортизированное время работы|-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex>|style="background-color:#FFF;padding: 2px 10px"| <tex> O(1) + </tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex>|style="background-color:#FFF;padding:2px 10px"| <tex>O(D[H]1) </tex> |-align="center"|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex>|style= "background-color:#FFF;padding:2px 10px"| <tex>O(D[H]\log n ) </tex>.|}
Поскольку, ранее мы показали== Недостатки и достоинства =='''Недостатки''':* Большое потребление памяти на узел(минимум 21 байт)* Большая константа времени работы, что делает ее малоприменимой для реальных задач* Некоторые операции в худшем случае могут работать за <tex> D[H] = O(log|H|) = O(logNn) </tex>, то соответствующие оценки доказаны.времени'''Достоинства''':* Одно из лучших асимптотических времен работы для всех операций
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - [[Категория: Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4* http://ru.wikipedia.org/wiki/Фибоначчиева_куча* http://www.intuit.ru/department/algorithms/dscm/7/2.html - INTUIT.ru* Визуализаторы на rain.ifmo.ru: http://rain.ifmo.ru/cat/view.php/vis/heapsструктуры данных]]* http[[Категория://www.cs.duke.edu/courses/fall05/cps230/L-11.pdfПриоритетные очереди]]
rollbackEdits.php mass rollback
'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} структура данных, отвечающая интерфейсу [[Приоритетные очереди#Операции | приоритетная очередь]]. Эта структура данных имеет меньшую [[Амортизационный анализ#Основные определения | амортизированную сложность]], чем такие приоритетные очереди как [[Биномиальная куча | биномиальная куча]] и [[Двоичная куча | двоичная куча]]. Изначально эта структура данных была разработана Майклом Фридманом<ref>[[wikipedia:en:Michael_Fredman | Майкл Фридман {{---}} Википедия]]</ref> и Робертом Тарьяном<ref>[[wikipedia:en:Robert_Tarjan | Роберт Тарьян {{---}} Википедия]]</ref> при работе по улучшению асимптотической сложности [[Алгоритм Дейкстры | алгоритма Дейкстры]]. Свое название Фибоначчиева куча получила из-за использования некоторых свойств чисел Фибоначчи<ref>[[wikipedia:en:Fibonacci_number | Числа Фибоначчи {{---}} Википедия]]</ref> в [[Амортизационный анализ#Метод потенциалов | потенциальном анализе]] этой реализации.= Фибоначчиевы = Структура ==Фибоначчиева куча {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одно из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья =не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.
{{Определение
|definition=
'''Фибоначчиево деревоСтепень вершины''' (англ. ''degree'') {{- биномиальное дерево--}} количество детей данной вершины. Далее будем обозначать как <tex>degree(x)</tex>, где у каждой вершины удалено не более одного ребенка<tex>x</tex> это вершина.
}}
{{Определение
|definition=
'''Фибоначчиево дерево порядка Степень кучи''' (англ. ''degree'') {{---}} наибольшая степень вершины этой кучи. Далее будем обозначать как <tex>ndegree(H)</tex>''' - биномиальное дерево порядка , где <tex>nH</tex>, из которого оно полученоэто куча.
}}
== Реализация ==
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]
Для возможности быстрого удаления элемента из произвольного места и объединением с другим списком будем хранить их в [[Список#Циклический список | циклическом двусвязном списке]]. Также будем хранить и все уровни поддерева. Исходя из этого структура каждого узла будет выглядеть вот так.
<code style="display:inline-block">
'''struct''' Node
'''int''' key <span style="color:#008000"> // ключ</span>
'''Node''' parent <span style="color:#008000"> // указатель на родительский узел</span>
'''Node''' child <span style="color:#008000"> // указатель на один из дочерних узлов</span>
'''Node''' left <span style="color:#008000"> // указатель на левый узел того же предка</span>
'''Node''' right <span style="color:#009000"> // указатель на правый узел того же предка</span>
'''int''' degree <span style="color:#008000"> // степень вершины</span>
'''boolean''' mark <span style="color:#008000">// был ли удален в процессе изменения ключа ребенок этой вершины)</span>
</code>Также стоит упомянуть, что нам нужен указатель только на одного ребенка, поскольку остальные хранятся в двусвязном списке с ним. Для доступа ко всей куче нам тоже нужен всего один элемент, поэтому разумно хранить именно указатель на минимум кучи (он обязательно один из корней), а для получения размера за константное время будем хранить размер кучи отдельно.
<code style="display:inline-block">
'''struct''' fibonacciHeap
'''int''' size <span style="color:#008000">// текущее количество узлов</span>
'''Node''' min <span style="color:#008000">// указатель на корень дерева с минимальным ключом</span>
</code>
==== Cоздание кучи ====
Инициализация кучи.
<code style="display:inline-block">
'''function''' buildHeap:
min <tex>= \varnothing</tex>
size = 0
</code>
==== Вставка элемента ====
Данная операция вставляет новый элемент в список корней правее минимума и при необходимости меняет указатель на минимум кучи.
<code style="display:inline-block">
'''function''' insert(x: '''int'''):
'''Node''' newNode <span style="color:#008000"> // создаем новый узел</span>
newNode.key = x <span style="color:#008000"> // инициализируем ключ нового узла</span>
'''if''' size = 0 <span style="color:#008000"> // если куче нет элементов, то только что добавленный минимальный</span>
min = newNode
min.left = newNode
min.right = newNode
'''else'''<span style="color:#008000"> // иначе аккуратно меняем указатели в списке, чтобы не перепутать указатели</span>
'''Node''' prevRight = min.right
min.right = newNode
newNode.left = min
newNode.right = prevRight
prevRight.left = newNode
'''if''' newNode.key < min.key
min = newNode <span style="color:#008000"> // меняем указатель на минимум, если надо</span>
newNode.parent <tex>= \varnothing</tex>
size++ <span style="color:#008000"> // не забываем увеличить переменную size </span>
</code>
==== Получение минимального элемента ====
Получение минимума всей кучи.
<code style="display:inline-block">
'''int''' getMin:
'''return''' min.key
</code>
==== Соедининение двух куч ====
Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую два списка вершины, которых подаются ей в качестве аргументов.
<code style="display:inline-block">
'''function''' unionLists(first: '''Node''', second: '''Node'''):
'''Node''' L = first.left <span style="color:#008000"> // аккуратно меняем указатели местами указатели</span>
'''Node''' R = second.right
second.right = first
first.left = second
L.right = R
R.left = L
</code>
Сливаем два корневых списка в один и обновляем минимум, если нужно.
<code style="display:inline-block">
'''function''' merge(that: '''fibonacciHeap'''):
'''if''' that.size = 0 <span style="color:#008000"> // если вторая куча пуста, нечего добавлять</span>
'''return'''
'''if''' size = 0 <span style="color:#008000"> // если наша куча пуста, то результатом будет вторая куча</span>
min = that.min
size = that.size
'''else'''
unionLists(min, that.min) <span style="color:#008000"> // объединяем два корневых списка</span>
size += that.size
'''if''' min <tex>= \varnothing</tex> '''or''' (that.min <tex> \neq \varnothing</tex> '''and''' that.min < min) <span style="color:#008000">// если минимум кучи изменился, то надо обновить указатель</span>
min = that.min
</code>
==== Удаление минимального элемента====
Первая рассматриваемая операция, в ходе которой значительно меняется структура кучи. Здесь используется вспомогательная процедура <tex>consolidate</tex>, благодаря которой собственно и достигается желанная амортизированная оценка. В данном случае <tex> min = \varnothing</tex> не рассматривается и считается нарушением предусловий <tex>deleteMin</tex>
<code style="display:inline-block">
'''int''' deleteMin:
'''Node''' prevMin = min
unionLists(min, min.child) <span style="color:#008000"> // список детей min объединяем с корневым</span>
'''Node''' L = min.left <span style="color:#008000"> // аккуратно удаляем min из списка</span>
'''Node''' R = min.right
L.right = R
R.left = L
'''if''' prevMin.right = prevMin <span style="color:#008000"> // отдельно рассмотрим случай с одним элементом</span>
min <tex>= \varnothing</tex>
'''return'''
min = min.right <span style="color:#008000"> // пока что перекинем указатель min на правого сына, а далее consolidate() скорректирует min в процессе выполнения</span>
consolidate()
size--
'''return''' prevMin.key
</code>
===== Прорежение деревьев =====
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> degree(H) + 1</tex> вершин.
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0 \dots D[H]] </tex>, где <tex> degree(H) </tex> {{---}} максимальная степень вершины в текущем корневом списке.
Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку. Подвешиваем мы его следующим образом: в корневой список добавляем корень минимальный из тех двух, а корень другого добавляем в список детей корневой вершины. Чтобы лучше понять этот процесс лучше воспользоваться [https://www.cs.usfca.edu/~galles/visualization/FibonacciHeap.html визуализатором]
<code style="display:inline-block">
'''function''' consolidate:
A = '''Node[]'''
A[min.degree] = min <span style="color:#008000"> // создаем массив и инициализируем его min</span>
'''Node''' current = min.right
'''while''' A[current.degree] <tex>\neq</tex> current<span style="color:#008000"> // пока элементы массива меняются</span>
'''if''' A[current.degree] <tex>= \varnothing</tex> <span style="color:#008000"> // если ячейка пустая, то положим в нее текущий элемент</span>
A[current.degree] = current
current = current.right
'''else''' <span style="color:#008000"> // иначе подвесим к меньшему из текущего корня и того, который лежит в ячейке другой</span>
'''Node''' conflict = A[current.degree]
'''Node''' addTo, adding
'''if''' conflict.key < current.key
addTo = conflict
adding = current
'''else'''
addTo = current
adding = conflict
unionLists(addTo.child, adding)
adding.parent = addTo
addTo.degree++
current = addTo
'''if''' min.key > current.key <span style="color:#008000"> // обновляем минимум, если нужно</span>
min = current
</code>
'''Пример'''
Изначально добавляем в нашу кучу <tex>7</tex> элементов <tex>56, 22, 84, 32, 85, 15, 16</tex>. После этого выполним операцию извлечения минимума:
[[File:Fibonacci-heap-consolidate-example-1.png|thumb|center|500px|Начальное состояние кучи]]
* Удалим минимальный элемент из циклического корневого списка и заведем массив <tex>A</tex> для дальнейшего прорежения.
[[File:Fibonacci-heap-consolidate-example-2.png|thumb|center|500px|Удаление мимимума и создание массива]]
* Начнем процесс протяжения с первого элемента {{---}} <tex>56</tex>. Его степень равна <tex>0</tex> поэтому запишем его адрес в нулевую ячейку массива.
[[File:Fibonacci-heap-consolidate-example-3.png|thumb|center|500px|Состояние массива после первой итерации]]
* Следующий элемент <tex>22</tex> тоже имеет степень <tex>0</tex>. Возникает конфликт, который решается подвешиванием к меньшему корню большего. То есть к <tex>22</tex> подвешиваем <tex>56</tex> и увеличиваем степень <tex>22</tex> на <tex>1</tex>. В итоге степень <tex>22</tex> равна <tex>1</tex>. Записываем адрес <tex>22</tex> по индексу <tex>1</tex> в массив.
[[File:Fibonacci-heap-consolidate-example-4.png.png|thumb|center|500px|Состояние после второй итерации]]
* Делаем тоже самое, что и на предыдущих итерациях, но теперь объединяем <tex>32</tex> и <tex>84</tex>
[[File:Fibonacci-heap-consolidate-example-5.png|thumb|center|500px|Состояние после четвертой итерации]]
* Теперь у нас два элемента со степенью <tex>1</tex> в корневом списке. Объединим их подвесив к меньшему корню {{---}} <tex>22</tex>, больший {{---}} <tex>32</tex>. Теперь степень <tex>22</tex> равна <tex>2</tex>, запишем на <tex>2</tex> позицию массива обновленное значение.
[[File:Fibonacci-heap-consolidate-example-6.png|thumb|center|500px|Состояние после пятой итерации]]
* Ну и наконец аналогично объедений последние два элемента.
[[File:Fibonacci-heap-consolidate-example-7.png|thumb|center|500px|Финальное состояние кучи]]
==== Уменьшение значения элемента ====
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой [[Список |список]]. Итак, сам алгоритм:
# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой [[Список |список]], и производим каскадное вырезание родителя.
<code style="display:inline-block">
'''function''' decreaseKey(x: '''Node''', newValue: '''int'''):
'''if''' newValue > x.parent.key <span style="color:#008000"> // если после изменения структура дерева сохранится, то меняем и выходим</span>
x.key = newValue
'''return'''
'''Node''' parent = x.parent <span style="color:#008000"> // иначе вызываем cut и cascadingCut</span>
cut(x)
cascadingCut(parent)
</code>
===== Вырезание =====
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).
<code style="display:inline-block">
'''function''' cut(x: '''Node''')
'''Node''' L = x.left
'''Node''' R = x.right
R.left = L <span style="color:#008000"> // аккуратно удаляем текущую вершину</span>
L.right = R
x.parent.degree--
'''if''' x.parent.child = x <span style="color:#008000"> // чтобы родитель не потерял ссылку на сыновей проверяем: </span>
'''if''' x.right = x. <span style="color:#008000"> // если узел который мы вырезаем содержится в родителе, то меняем его на соседний</span>
x.parent.child <tex>= \varnothing</tex> <span style="color:#008000"> // иначе у родителя больше нет детей</span>
'''else'''
x.parent.child = x.right
x.right = x
x.left = x
x.parent <tex>= \varnothing</tex>
unionLists(min, x) <span style="color:#008000"> // вставляем наше поддерево в корневой список</span>
</code>
===== Каскадное вырезание =====
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]
<code style="display:inline-block">
'''function''' cascadingCut(x: '''Node''')
'''while''' x.mark = '''true''' <span style="color:#008000"> // пока у нас помеченые вершины вырезаем их</span>
cut(x)
x = x.parent
x.mark = true <span style="color:#008000"> // последнюю вершину нужно пометить {{---}} у нее удаляли ребенка</span>
</code>
'''Пример'''
Рисунок иллюстрирует пример каскадного вырезания:
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой [[Список |список]] и помечаем ее родителя.
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.
==== Удаление элемента ====
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума.
<code style="display:inline-block">
'''function''' delete(x: '''Node''')
decreaseKey(x, <tex>-\infty</tex>)
deleteMin()
</code>
== Время работы ==
==== Потенциал ====
Для анализа производительности операций введем потенциал для фибоначчиевой кучи как <tex> \Phi = trees + 2 * marked </tex>, где <tex> trees </tex> {{---}} количество элементов в корневом списке кучи, а <tex> marked </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.
==== Cоздание кучи ====
Очевидно, что реальное время работы {{---}} <tex> O(1) </tex>.
==== Вставка элемента ====
Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> trees(H') = trees(H) + 1 </tex> и <tex> marked(H') = marked(H) </tex>. Следовательно, увеличение потенциала составляет <tex> (trees(H) + 1 + 2 * marked(H)) - (trees(H) + 2 * marked(H)) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.
==== Получение минимального элемента ====
Истинное время работы {{---}} <tex> O(1) </tex>.
==== Соедининение двух куч ====
Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.
==== Удаление минимального элемента====
Для доказательства времени работы этого алгоритма нам понадобится доказать несколько вспомогательных утверждений.
{{Лемма
|id=Лемма1
|statement=Для всех целых <tex> n \geqslant 2</tex>
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,
где <tex> F_n </tex> {{---}} <tex> n </tex> -ое число Фибоначчи, определяемое формулой:
<tex>
F_n =
{{Лемма
|id=Лемма2
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.
|proof=
Докажем это утверждение по индукции.
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.
При <tex>n = 0</tex>
<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex>
Но по предыдущей [[#Лемма1|лемме]] <tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex>}} = Фибоначчиевы кучи =:
<tex>1 + \sum\limits_{i=0}^{Определение|definitionn-2} F_i ='''Фибоначчиева куча''' - набор фибоначчиевых деревьевF_n</tex>. Следовательно, упорядоченных в соответствии со свойством неубывающей кучи.<tex>s_n \geqslant F_n</tex>
}}
{{Лемма
|id=Лемма3
|statement= <tex>F_n =O(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex>
|proof=
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex>
При <tex>n = Операции =1</tex>
<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>, что также верно.
<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>
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} =-\varphi + \varphi^{2} = Слияние ==1</tex>
Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(degree)+O(degree)=O(degree) </tex>. По доказанной выше [[File:Cascading-cut.png#Лемма4|thumb|600px|Каскадное вырезаниелемме]]<tex>O(degree) = O(\log(n))</tex>.
В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((trees + k) + 2 * (marked + k - 2)) - (trees + 2 * marked) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.==== Удаление вершины элемента ====Амортизированное время работы: <tex> O(1) + O(degree) =O(degree) </tex>.
= Ссылки =См. также ==* [[Приоритетные очереди]]* [[Двоичная куча]]* [[Биномиальная куча]]* [[Левосторонняя куча]]* [[Тонкая куча]]* [[Толстая куча на избыточном счетчике]]* [[Куча Бродала-Окасаки]]== Примечания ==<references/>== Источники информации ==* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4* [[wikipedia:en:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]* [[wikipedia:en:Fibonacci heap|Фибоначчиева куча {{---}} Википедия]]* [https://www.cs.usfca.edu/~galles/visualization/FibonacciHeap.html Fibonacci heap visualization]* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps {{---}} Duke University]* [https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf Fibonacci Heaps {{---}} Princeton University]
