Фибоначчиева куча — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 126 промежуточных версий 23 участников)
Строка 1: Строка 1:
'''Фибоначчиевы кучи''' - модификация [[Биномиальная_куча|биномиальных куч]], в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.
+
'''Фибоначчиева куча''' (англ. ''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=
 
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
+
'''Степень кучи''' (англ. ''degree'')  {{---}} наибольшая степень вершины этой кучи. Далее будем обозначать как <tex>degree(H)</tex>, где <tex>H</tex> это куча.
 
}}
 
}}
  
{{Лемма
+
== Реализация ==
|statement=
+
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
+
Для возможности быстрого удаления элемента из произвольного места и объединением с другим списком будем хранить их в [[Список#Циклический список | циклическом двусвязном списке]]. Также будем хранить и все уровни поддерева. Исходя из этого структура каждого узла будет выглядеть вот так.
|proof=
+
<code style="display:inline-block">
Для рангов 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.
+
'''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> k </tex>
+
===== Каскадное вырезание =====
 +
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<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> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.
+
'''Пример'''
  
Эта сумма, в свою очередь, равна <tex> F_k </tex>
+
Рисунок иллюстрирует пример каскадного вырезания:
}}
 
  
Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куча с <tex> N </tex> вершинами есть <tex> O(logN) </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> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).
+
==== Удаление элемента ====
 +
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума.
 +
<code style="display:inline-block">
 +
'''function''' delete(x: '''Node''')
 +
    decreaseKey(x, <tex>-\infty</tex>)
 +
    deleteMin()
 +
</code>
  
Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>
+
== Время работы ==
 +
==== Потенциал ====
 +
Для анализа производительности операций введем потенциал для фибоначчиевой кучи как <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] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.
+
при <tex>n = 2</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] </tex>, указывающего на минимальную вершину в куче.
+
При <tex>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] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.
+
Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.
 +
Пусть в нашем дереве удалено поддерево порядка <tex>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] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.
+
Но по предыдущей [[#Лемма1|лемме]] :
  
== Слияние ==
+
<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 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.
+
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.
  
== Извлечение минимума ==
+
При <tex>n = 1</tex>
  
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </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>, что также верно.
  
=== "Уплотнение" (Consolidate) ===
+
По индукции предполагаем, что <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> O(D[H]) </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> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </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> d </tex> Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.
+
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex>
  
Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </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 =O(\varphi^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]) </tex> действий.
+
{{Лемма
 +
|id=Лемма4
 +
|statement=Максимальная степень <tex>degree</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>O(\varphi^k)</tex>.
 +
То есть
  
== Уменьшение ключа ==
+
<tex>n \geqslant \varphi^{k}</tex>
  
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>.  Хотим, чтобы вершина не всплывала до корня. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:
+
Логарифмируя по основанию <tex>\varphi</tex>, получаем
  
# Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
+
<tex>\log_{\varphi}n \geqslant k</tex>
# Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.
 
  
=== Вырезание вершины ===
+
Таким образом, максимальная степень <tex>degree</tex> произвольной вершины равна <tex>O(\log n)</tex>.
 +
}}
  
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем <tex> degree[p[x]] </tex> и снимаем пометку с текущей вершины (<tex> mark[x] = false </tex>).
+
Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(degree)+O(degree)=O(degree) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(degree) = O(\log(n))</tex>.
  
=== Каскадное вырезание ===
+
Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(degree) </tex>. Докажем это:
  
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.
+
Изначально в корневом списке было не более <tex> degree + trees - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>trees</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> degree </tex>. В ходе операции <tex> \mathrm {consolidate} </tex> мы сделали <tex> O(degree + trees) </tex> слияний деревьев. Потенциал перед извлечением минимума равен <tex> trees + 2 * marked </tex>, а после не превышает <tex> degree + 1 + 2 * marked</tex>, поскольку в корневом списке остается не более  <tex> degree + 1 </tex> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит
  
Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
+
<tex> O(degree + trees) + (degree + 1 + 2 * marked) - (trees + 2 * marked) = O(degree) + O(trees) - trees</tex>
  
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2 * k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>
+
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(degree) </tex>
 +
==== Уменьшение значения элемента ====
 +
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
  
На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.
+
Пусть мы вызвали процедуру каскадного вырезания подверглось <tex> k </tex> раз. Так как реальное время работы каждой итерации <tex> \mathrm {cascadingCut} </tex> составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>.  
  
Иначе, <tex> mark[p[x]] == true </tex> и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.
+
Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <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} = ((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> -\infty </tex> и последующим извлечением минимума. Амортизированное время работы: <tex> O(1) + O(D[H]) = O(D[H]) </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>\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(1)</tex>
 +
|-align="center"
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex>  
 +
|}
  
Поскольку, ранее мы показали, что <tex> D[H] = O(log|H|) = O(logN) </tex>, то соответствующие оценки доказаны.
+
== Недостатки и достоинства ==
 +
'''Недостатки''':
 +
* Большое потребление памяти на узел(минимум 21 байт)
 +
* Большая константа времени работы, что делает ее малоприменимой для реальных задач
 +
* Некоторые операции в худшем случае могут работать за <tex>O(n)</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
 

Текущая версия на 19:39, 4 сентября 2022

Фибоначчиева куча (англ. Fibonacci heap) — структура данных, отвечающая интерфейсу приоритетная очередь. Эта структура данных имеет меньшую амортизированную сложность, чем такие приоритетные очереди как биномиальная куча и двоичная куча. Изначально эта структура данных была разработана Майклом Фридманом[1] и Робертом Тарьяном[2] при работе по улучшению асимптотической сложности алгоритма Дейкстры. Свое название Фибоначчиева куча получила  из-за использования некоторых свойств чисел Фибоначчи[3] в потенциальном анализе этой реализации.

Структура

Фибоначчиева куча — набор из подвешенных деревьев удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одно из главных преимуществ Фибоначчиевой кучи — гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.

Определение:
Степень вершины (англ. degree) — количество детей данной вершины. Далее будем обозначать как [math]degree(x)[/math], где [math]x[/math] это вершина.


Определение:
Степень кучи (англ. degree) — наибольшая степень вершины этой кучи. Далее будем обозначать как [math]degree(H)[/math], где [math]H[/math] это куча.


Реализация

Пример фибоначчиевой кучи

Для возможности быстрого удаления элемента из произвольного места и объединением с другим списком будем хранить их в циклическом двусвязном списке. Также будем хранить и все уровни поддерева. Исходя из этого структура каждого узла будет выглядеть вот так.

struct Node
   int key      // ключ
   Node parent  // указатель на родительский узел
   Node child   // указатель на один из дочерних узлов
   Node left    // указатель на левый узел того же предка
   Node right   // указатель на правый узел того же предка
   int degree   // степень вершины
   boolean mark // был ли удален в процессе изменения ключа ребенок этой вершины)

Также стоит упомянуть, что нам нужен указатель только на одного ребенка, поскольку остальные хранятся в двусвязном списке с ним. Для доступа ко всей куче нам тоже нужен всего один элемент, поэтому разумно хранить именно указатель на минимум кучи (он обязательно один из корней), а для получения размера за константное время будем хранить размер кучи отдельно.

struct fibonacciHeap
   int size // текущее количество узлов
   Node min // указатель на корень дерева с минимальным ключом 

Cоздание кучи

Инициализация кучи.

function buildHeap:
   min [math]= \varnothing[/math] 
   size = 0

Вставка элемента

Данная операция вставляет новый элемент в список корней правее минимума и при необходимости меняет указатель на минимум кучи.

function insert(x: int):
   Node newNode                // создаем новый узел 
   newNode.key = x             // инициализируем ключ нового узла
   if size = 0                // если куче нет элементов, то только что добавленный минимальный
       min = newNode
       min.left = newNode
       min.right = newNode
   else                        // иначе аккуратно меняем указатели в списке, чтобы не перепутать указатели
       Node prevRight = min.right 
       min.right = newNode
       newNode.left = min 
       newNode.right = prevRight 
       prevRight.left = newNode 
   if newNode.key < min.key
       min = newNode           // меняем указатель на минимум, если надо
   newNode.parent [math]= \varnothing[/math] 
   size++                      // не забываем увеличить переменную size 

Получение минимального элемента

Получение минимума всей кучи.

int getMin:
   return min.key

Соедининение двух куч

Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию [math]unionLists[/math] логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.

function unionLists(first: Node, second: Node):
   Node L = first.left               // аккуратно меняем указатели местами указатели
   Node R = second.right
   second.right = first
   first.left = second
   L.right = R
   R.left = L

Сливаем два корневых списка в один и обновляем минимум, если нужно.

function merge(that: fibonacciHeap):
   if that.size = 0               // если вторая куча пуста, нечего добавлять
       return
   if size = 0                    // если наша куча пуста, то результатом будет вторая куча
       min = that.min
       size = that.size
   else 
       unionLists(min, that.min)   // объединяем два корневых списка
       size += that.size
   if min [math]= \varnothing[/math] or (that.min [math] \neq \varnothing[/math] and that.min < min) // если минимум кучи изменился, то надо обновить указатель
       min = that.min

Удаление минимального элемента

Первая рассматриваемая операция, в ходе которой значительно меняется структура кучи. Здесь используется вспомогательная процедура [math]consolidate[/math], благодаря которой собственно и достигается желанная амортизированная оценка. В данном случае [math] min = \varnothing[/math] не рассматривается и считается нарушением предусловий [math]deleteMin[/math]

int deleteMin:
   Node prevMin = min 
   unionLists(min, min.child)    // список детей min объединяем с корневым
   Node L = min.left             // аккуратно удаляем min из списка
   Node R = min.right
   L.right = R
   R.left = L
   if prevMin.right = prevMin   // отдельно рассмотрим случай с одним элементом
       min [math]= \varnothing[/math]
       return
   min = min.right               // пока что перекинем указатель min на правого сына, а далее consolidate() скорректирует min в процессе выполнения
   consolidate()
   size-- 
   return prevMin.key

Прорежение деревьев

Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более [math] degree(H) + 1[/math] вершин.

Для этого возьмем массив списков указателей на корни деревьев [math] A[0 \dots D[H]] [/math], где [math] degree(H) [/math] — максимальная степень вершины в текущем корневом списке.

Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна [math] d [/math]. Если в соответствующей ячейке [math]A[/math] еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна [math] d + 1 [/math]. Продолжаем, пока не найдем свободную ячейку. Подвешиваем мы его следующим образом: в корневой список добавляем корень минимальный из тех двух, а корень другого добавляем в список детей корневой вершины. Чтобы лучше понять этот процесс лучше воспользоваться визуализатором

function consolidate:
   A = Node[]
   A[min.degree] = min                    // создаем массив и инициализируем его min
   Node current = min.right
   while A[current.degree] [math]\neq[/math] current     // пока элементы массива меняются
       if A[current.degree] [math]= \varnothing[/math]         // если ячейка пустая, то положим в нее текущий элемент
           A[current.degree] = current
           current = current.right
       else                               // иначе подвесим к меньшему из текущего корня и того, который лежит в ячейке другой
           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          // обновляем минимум, если нужно
           min = current     

Пример

Изначально добавляем в нашу кучу [math]7[/math] элементов [math]56, 22, 84, 32, 85, 15, 16[/math]. После этого выполним операцию извлечения минимума:

Начальное состояние кучи


  • Удалим минимальный элемент из циклического корневого списка и заведем массив [math]A[/math] для дальнейшего прорежения.


Удаление мимимума и создание массива


  • Начнем процесс протяжения с первого элемента — [math]56[/math]. Его степень равна [math]0[/math] поэтому запишем его адрес в нулевую ячейку массива.


Состояние массива после первой итерации


  • Следующий элемент [math]22[/math] тоже имеет степень [math]0[/math]. Возникает конфликт, который решается подвешиванием к меньшему корню большего. То есть к [math]22[/math] подвешиваем [math]56[/math] и увеличиваем степень [math]22[/math] на [math]1[/math]. В итоге степень [math]22[/math] равна [math]1[/math]. Записываем адрес [math]22[/math] по индексу [math]1[/math] в массив.
Состояние после второй итерации


  • Делаем тоже самое, что и на предыдущих итерациях, но теперь объединяем [math]32[/math] и [math]84[/math]


Состояние после четвертой итерации


  • Теперь у нас два элемента со степенью [math]1[/math] в корневом списке. Объединим их подвесив к меньшему корню — [math]22[/math], больший — [math]32[/math]. Теперь степень [math]22[/math] равна [math]2[/math], запишем на [math]2[/math] позицию массива обновленное значение.


Состояние после пятой итерации


  • Ну и наконец аналогично объедений последние два элемента.


Финальное состояние кучи

Уменьшение значения элемента

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

  1. Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.
  2. Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

function decreaseKey(x: Node, newValue: int):
   if newValue > x.parent.key  // если после изменения структура дерева сохранится, то меняем и выходим
       x.key = newValue
       return
   Node parent = x.parent     // иначе вызываем cut и cascadingCut
   cut(x)
   cascadingCut(parent)

Вырезание

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

function cut(x: Node)
   Node L = x.left
   Node R = x.right
   R.left = L                // аккуратно удаляем текущую вершину
   L.right = R
   x.parent.degree--
   if x.parent.child = x   // чтобы родитель не потерял ссылку на сыновей проверяем: 
       if x.right = x.     // если узел который мы вырезаем содержится в родителе, то меняем его на соседний
           x.parent.child [math]= \varnothing[/math]  // иначе у родителя больше нет детей
       else
           x.parent.child = x.right
   x.right = x
   x.left = x
   x.parent [math]= \varnothing[/math]
   unionLists(min, x)        // вставляем наше поддерево в корневой список

Каскадное вырезание

Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел ([math] x.mark = false [/math]), то мы помечаем эту вершину ([math] x.mark = true [/math]) и прекращаем выполнение операции. В противном случае применяем операцию [math]\mathrm {cut}[/math] для текущей вершины и запускаем каскадное вырезание от родителя.

Пример каскадного вырезания

function cascadingCut(x: Node)
   while x.mark = true  // пока у нас помеченые вершины вырезаем их
       cut(x)
       x = x.parent
   x.mark = true         // последнюю вершину нужно пометить — у нее удаляли ребенка

Пример

Рисунок иллюстрирует пример каскадного вырезания:

  • Изначально, куча состояла из [math]3[/math] фибоначчиевых деревьев. У вершины с ключом [math]24[/math] отсутствует [math]1[/math] ребенок.
  • Уменьшаем ключ [math]26[/math] до [math]5[/math] и делаем операцию [math]\mathrm {cut}[/math] этого дерева. Получаем кучу с [math]4[/math] деревьями и новым минимумом. Но у вершины с ключом [math]24[/math] был удален второй ребенок, поэтому запускам операцию [math]\mathrm {cascadingCut}[/math] для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.
  • У вершины с ключом [math]7[/math] удален лишь один ребенок, поэтому операция [math]\mathrm {cascadingCut}[/math] от нее не запускается. В итоге, получаем кучу, состоящую из [math]5[/math] фибоначчиевых деревьев.

Удаление элемента

Удаление вершины реализуется через уменьшение ее ключа до [math] -\infty [/math] и последующим извлечением минимума.

function delete(x: Node)
   decreaseKey(x, [math]-\infty[/math])
   deleteMin()

Время работы

Потенциал

Для анализа производительности операций введем потенциал для фибоначчиевой кучи как [math] \Phi = trees + 2 * marked [/math], где [math] trees [/math] — количество элементов в корневом списке кучи, а [math] marked [/math] — количество вершин, у которых удален один ребенок (то есть вершин с пометкой [math] x.mark = true [/math]). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.

Cоздание кучи

Очевидно, что реальное время работы — [math] O(1) [/math].

Вставка элемента

Для оценки амортизированной стоимости операции рассмотрим исходную кучу [math] H [/math] и получившуюся в результате вставки нового элемента кучу [math] H' [/math]. [math] trees(H') = trees(H) + 1 [/math] и [math] marked(H') = marked(H) [/math]. Следовательно, увеличение потенциала составляет [math] (trees(H) + 1 + 2 * marked(H)) - (trees(H) + 2 * marked(H)) = 1 [/math]. Так как реальное время работы составляет [math] O(1) [/math], то амортизированная стоимость данной операции также равна [math] O(1) [/math].

Получение минимального элемента

Истинное время работы — [math] O(1) [/math].

Соедининение двух куч

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

Удаление минимального элемента

Для доказательства времени работы этого алгоритма нам понадобится доказать несколько вспомогательных утверждений.

Лемма:
Для всех целых [math] n \geqslant 2[/math]

[math] F_n = 1 + \sum\limits_{i=0}^{n-2} F_i [/math], где [math] F_n [/math][math] n [/math]-ое число Фибоначчи, определяемое формулой:

[math] F_n = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ F_{n-1} + F_{n-2}, & n \geqslant 2 \end{cases} [/math]
Доказательство:
[math]\triangleright[/math]

Докажем лемму по индукции:

при [math]n = 2[/math]

[math]F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1[/math], что действительно верно.

По индукции предполагаем, что [math]F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i [/math]. Тогда

[math]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[/math]
[math]\triangleleft[/math]
Лемма:
Фибоначчиево дерево порядка [math]n[/math] содержит не менее [math]F_n[/math] вершин.
Доказательство:
[math]\triangleright[/math]

Докажем это утверждение по индукции. Пусть [math]s_n[/math] — минимальный размер фибоначчиева дерева порядка [math]n[/math].

При [math]n = 0[/math]

[math]s_0 = 1 \gt F_0[/math].

При [math]n = 1[/math]

[math]s_1 = 1 = F_1[/math].

Предположим по индукции, что для всех [math]i \lt n \ s_i \geqslant F_i[/math]. Пусть в нашем дереве удалено поддерево порядка [math]n - 1[/math]. Тогда

[math]s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i[/math]

Но по предыдущей лемме :

[math]1 + \sum\limits_{i=0}^{n-2} F_i = F_n[/math]. Следовательно, [math]s_n \geqslant F_n[/math]
[math]\triangleleft[/math]
Лемма:
[math]F_n =O(\varphi^n)[/math], где [math] \varphi = \frac {1 + \sqrt 5} {2}[/math]
Доказательство:
[math]\triangleright[/math]

Для начала докажем, что [math]F_n =[/math] [math]\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}[/math]

Используем для этого математическую индукцию.

При [math]n = 0[/math]

[math]F_0 =[/math] [math]\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0[/math], что верно.

При [math]n = 1[/math]

[math]F_1 =[/math] [math]\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[/math], что также верно.

По индукции предполагаем, что [math]F_{n-1} =[/math] [math]\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}[/math] и [math]F_{n-2} =[/math] [math]\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}[/math]. Тогда

[math]F_n = F_{n-1} + F_{n-2} =[/math] [math]\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =[/math]

[math]= \frac {1} {\sqrt 5}[/math] [math](\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) [/math] [math]= \frac {1} {\sqrt 5}[/math] [math](\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))[/math]

Подставив вместо [math]\varphi[/math] его значение, нетрудно убедится, что [math]\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1[/math]

Поскольку [math]\left\vert (-\varphi)^{-1} \right\vert \lt 1[/math], то выполняются неравенства [math]\frac {(-\varphi)^{-n}} {\sqrt 5} \lt \frac {1} {\sqrt 5} \lt \frac {1} {2}[/math]. Таким образом, [math]n[/math]-ое число Фибоначчи равно [math]\frac {\varphi^{n}} {\sqrt 5}[/math], округленному до ближайшего целого числа. Следовательно, [math]F_n =O(\varphi^n)[/math].
[math]\triangleleft[/math]


Лемма:
Максимальная степень [math]degree[/math] произвольной вершины в фибоначчиевой куче с [math]n[/math] вершинами равна [math]O(\log n)[/math]
Доказательство:
[math]\triangleright[/math]

Пусть [math]x[/math] — произвольная вершина в фибоначчиевой куче с [math]n[/math] вершинами, и пусть [math]k[/math] — степень вершины [math]x[/math]. Тогда по доказанному выше в дереве, корень которого [math]x[/math], содержится не менее [math]F_k[/math] вершин, что в свою очередь по лемме равно [math]O(\varphi^k)[/math]. То есть

[math]n \geqslant \varphi^{k}[/math]

Логарифмируя по основанию [math]\varphi[/math], получаем

[math]\log_{\varphi}n \geqslant k[/math]

Таким образом, максимальная степень [math]degree[/math] произвольной вершины равна [math]O(\log n)[/math].
[math]\triangleleft[/math]

Итоговая асимптотика операции [math]\mathrm {extraxtMin}[/math], учитывая и вспомогательную функцию [math] \mathrm {consolidate} [/math], время работы которой доказывается ниже, равно: [math] O(1)+O(degree)+O(degree)=O(degree) [/math]. По доказанной выше лемме [math]O(degree) = O(\log(n))[/math].

Учетная стоимость [math] \mathrm {consolidate} [/math] равна [math] O(degree) [/math]. Докажем это:

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

[math] O(degree + trees) + (degree + 1 + 2 * marked) - (trees + 2 * marked) = O(degree) + O(trees) - trees[/math]

Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка — [math] O(degree) [/math]

Уменьшение значения элемента

Докажем, что амортизированное время работы операции [math] \mathrm {decreaseKey} [/math] есть [math] O(1) [/math]. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания подверглось [math] k [/math] раз. Так как реальное время работы каждой итерации [math] \mathrm {cascadingCut} [/math] составляет [math] O(1) [/math], то реальное время работы операции [math] \mathrm {decreaseKey} [/math][math] O(k) [/math].

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

В итоге, изменение потенциала составляет: [math] \Phi_i - \Phi_{i - 1} = ((trees + k) + 2 * (marked + k - 2)) - (trees + 2 * marked) = 4 - k [/math]. Следовательно, амортизированная стоимость не превышает [math] O(k) + 4 - k [/math]. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции [math] \mathrm {decreaseKey} [/math] равна [math] O(1) [/math].

Удаление элемента

Амортизированное время работы: [math] O(1) + O(degree) = O(degree) [/math].

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

Итоговая таблица

Операция Амортизированная сложность
[math]\mathrm {makeHeap}[/math] [math]O(1)[/math]
[math]\mathrm {insert}[/math] [math]O(1)[/math]
[math]\mathrm {getMin}[/math] [math]O(1)[/math]
[math]\mathrm {merge}[/math] [math]O(1)[/math]
[math]\mathrm {extractMin}[/math] [math]O(\log n )[/math]
[math]\mathrm {decreaseKey}[/math] [math]O(1)[/math]
[math]\mathrm {delete}[/math] [math]O(\log n )[/math]

Недостатки и достоинства

Недостатки:

  • Большое потребление памяти на узел(минимум 21 байт)
  • Большая константа времени работы, что делает ее малоприменимой для реальных задач
  • Некоторые операции в худшем случае могут работать за [math]O(n)[/math] времени

Достоинства:

  • Одно из лучших асимптотических времен работы для всех операций

См. также

Примечания

Источники информации