Изменения

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

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

{{Лемма== Реализация == [[File:Fibonacci-heap.png|statementthumb|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> k min = \varnothing</tex> содержит не менее рассматривается и считается нарушением предусловий <tex> F_k 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> k = \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 |proofпроцесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <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> F_0 \ge 1) и снимаем пометку с текущей вершины (<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"> // если узел который мы вырезаем содержится в родителе, F_1 то меняем его на соседний</span> x.parent.child <tex>= \ge 1 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> k 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> F_k = \Omega(\varphi^k) mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex>был удален второй ребенок, где поэтому запускам операцию <tex> \varphi = \frac mathrm {1 + \sqrt 5cascadingCut}2 </tex>для этой вершины: вырезаем ее, то максимальная степень помещаем в корневой [[Список |список]] и помечаем ее родителя.* У вершины в фибоначчиевой куча с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex> N \mathrm {cascadingCut}</tex> вершинами есть от нее не запускается. В итоге, получаем кучу, состоящую из <tex> O(logN) 5</tex>фибоначчиевых деревьев.

Каждая вершина ==== Удаление элемента ====Удаление вершины реализуется через уменьшение ее ключа до <tex> x -\infty </tex> знает своего родителя и последующим извлечением минимума.<code style="display:inline-block"> '''function''' delete(x: '''Node''') decreaseKey(x, <tex> p[x] -\infty</tex>) и какого-нибудь своего ребенка deleteMin(<tex> child[x] )</texcode>).

Дети любой вершины связаны == Время работы ====== Потенциал ====Для анализа производительности операций введем потенциал для фибоначчиевой кучи как <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 =\begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ F_{n-1} + F_{n-2}, & n \geqslant 2\end{cases} </tex>|proof=Докажем лемму по индукции:

Также в любой вершине хранятся поля при <tex> degree[x], \, mark[x] n = 2</tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.

<tex>F_2 = Фибоначчиевы кучи 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.

По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{Определениеn-3} F_i </tex>. Тогда |definition<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>

Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list){{Лемма|id=Лемма2|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин. В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня|proof=Докажем это утверждение по индукции.Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.

Доступ к куче осуществляется с помощью указателя При <tex> min[H] n = 0</tex>, указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа<tex>s_0 = 1 > F_0</tex>.

При <tex>n = Операции =1</tex>

<tex>s_1 =1 = Потенциал ==F_1</tex>.

Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>Предположим по индукции, как количество элементов в корневом списке (что для всех <tex> t[H] i </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true n \ s_i \, (m[H]) geqslant F_i</tex>. Подходящую константу Пусть в нашем дереве удалено поддерево порядка <tex> C n - 1</tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.Тогда

<tex>s_n =1 + \sum\limits_{i= Создание кучи =0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex>

Создается новый пустой корневой список, в <tex> minНо по предыдущей [H[#Лемма1|лемме]] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.:

<tex>1 + \sum\limits_{i=0}^{n-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> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>Используем для этого математическую индукцию.

При <tex>n == Вставка элемента ==0</tex>

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 <tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (создание кучи-\varphi) + 2 (слияние куч + релаксация минимума) + ^0} {\sqrt 5} = \frac {1 - 1(изменение потенциала) } {\sqrt 5} = 40</tex>, что верно.

При <tex>n == Извлечение минимума ==1</tex>

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] F_1 =</tex>, удалим эту вершину. Ее поддеревья (их не более, чем <texdpi="160"> D[H] </tex>\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.

По индукции предполагаем, что <tex>F_{n-1} ==</tex> <tex dpi= "Уплотнение160" >\frac {\varphi^{n-1} - (Consolidate-\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> OF_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (D[H]-\varphi) ^{2-n}} {\sqrt 5} =</tex> вершин.

Для этого возьмем массив списков указателей на корни деревьев <texdpi="160"> A[0..D[H]] = \frac {1} {\sqrt 5}</tex>, где <tex> D[H] (\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <texdpi="160"> D[H] = O\frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (logN-\varphi)^{-n}(-\varphi + \varphi^{2})) </tex>.

Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна Подставив вместо <tex> d \varphi</tex> Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другомуего значение, и пытаемся также добавить деревонетрудно убедится, степень корня которого уже равна что <tex> d \varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1 </tex>. Продолжаем, пока не найдем свободную ячейку.

Учетная стоимость Поскольку <tex> Consolidate \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 =O(D[H]\varphi^n) </tex>. Докажем это:}}

На языке метода предоплаты: Положим у каждой {{Лемма|id=Лемма4|statement=Максимальная степень <tex>degree</tex> произвольной вершины-ребенка удаленной монету. Это в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex> O(D[H]\log n) </tex> действий|proof=Пусть <tex>x</tex> {{---}} произвольная вершина в фибоначчиевой куче с <tex>n</tex> вершинами, и пусть <tex>k</tex> {{---}} степень вершины <tex>x</tex>. Теперь: у каждой вершины Тогда по [[#Лемма2|доказанному выше]] в корневом списке лежит монетадереве, потратим ее на то, чтобы провести процедуру корень которого <tex> Consolidate x</tex>. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого содержится не менее <tex>F_k</tex> O(Dвершин, что в свою очередь по [[H#Лемма3|лемме]) + ] равно <tex>O(D[H]\varphi^k) </tex> действий.То есть

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

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

При вырезании вершины мы удаляем ее из списка детей своего родителяИтоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, уменьшаем учитывая и вспомогательную функцию <tex> degree[p[x]] \mathrm {consolidate} </tex> и снимаем пометку с текущей вершины , время работы которой доказывается ниже, равно: <tex> O(1)+O(degree)+O(degree)=O(degree) </tex> mark. По доказанной выше [x[#Лемма4|лемме]] <tex>O(degree) = false O(\log(n))</tex>).

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

Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(degree + trees) + (degree + 1+ 2 * marked) - (trees + 2 * marked) = O(degree) + O(trees) - trees</tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

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

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

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

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

= Ссылки =См. также ==* [[Приоритетные очереди]]* [[Двоичная куча]]* [[Биномиальная куча]]* [[Левосторонняя куча]]* [[Тонкая куча]]* [[Толстая куча на избыточном счетчике]]* [[Куча Бродала-Окасаки]]== Примечания ==<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]

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - [[Категория: Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 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Приоритетные очереди]]