Викиконспекты - Вклад участника [ru]

Фибоначчиева куча

2018-11-28T08:32:09Z

92.242.59.6: /* Реализация */

'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} структура данных, отвечающая интерфейсу [[Приоритетные очереди#Операции | приоритетная очередь]]. Эта структура данных имеет меньшую [[Амортизационный анализ#Основные определения | амортизированную сложность]], чем такие приоритетные очереди как [[Биномиальная куча | биномиальная куча]] и [[Двоичная куча | двоичная куча]]. Изначально эта структура данных была разработана Майклом Фридманом<ref>[[wikipedia:en:Michael_Fredman | Майкл Фридман {{---}} Википедия]]</ref> и Робертом Тарьяном<ref>[[wikipedia:en:Robert_Tarjan | Роберт Тарьян {{---}} Википедия]]</ref> при работе по улучшению асимптотической сложности [[Алгоритм Дейкстры | алгоритма Дейкстры]]. Свое название Фибоначчиева куча получила из-за использования некоторых свойств чисел Фибоначчи<ref>[[wikipedia:en:Fibonacci_number | Числа Фибоначчи {{---}} Википедия]]</ref> в [[Амортизационный анализ#Метод потенциалов | потенциальном анализе]] этой реализации.
== Структура ==
Фибоначчиева куча {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одним из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.
{{Определение
|definition=
'''Степень вершины''' (англ. ''degree'') {{---}} количество детей данной вершины. Далее будем обозначать как <tex>degree(x)</tex>, где <tex>x</tex> это вершина.
}}
{{Определение
|definition=
'''Степень кучи''' (англ. ''degree'') {{---}} наибольшая степень вершины этой кучи. Далее будем обозначать как <tex>degree(H)</tex>, где <tex>H</tex> это куча.
}}
== Реализация ==
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]
Для возможности быстрого удаления элемента из произвольного места и объединением с другим списком будем хранить их в [[Список#Циклический список | циклическом двусвязном списке]]. Также будем хранить и все уровни поддерева. Исходя из этого структура каждого узла будет выглядеть вот так.
<code style="display:inline-block">
'''struct''' Node
'''int''' key // ключ
'''Node''' parent // указатель на родительский узел
'''Node''' child // указатель на один из дочерних узлов
'''Node''' left // указатель на левый узел того же предка
'''Node''' right // указатель на правый узел того же предка
'''int''' degree // степень вершины
'''boolean''' mark // был ли удален в процессе изменения ключа ребенок этой вершины)
</code>Также стоит упомянуть, что нам нужен указатель только на одного ребенка, поскольку остальные хранятся в двусвязном списке с ним. Для доступа ко всей куче нам тоже нужен всего один элемент, поэтому разумно хранить именно указатель на минимум кучи (он обязательно один из корней), а для получения размера за константное время будем хранить размер кучи отдельно.
<code style="display:inline-block">
'''struct''' fibonacciHeap
'''int''' size // текущее количество узлов
'''Node''' min // указатель на корень дерева с минимальным ключом
</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 // создаем новый узел
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 <tex>= \varnothing</tex>
size++ // не забываем увеличить переменную size 
</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 // аккуратно меняем указатели местами указатели
'''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 // если вторая куча пуста, нечего добавлять
'''return'''
'''if''' size = 0 // если наша куча пуста, то результатом будет вторая куча
min = that.min
size = that.size
'''else'''
unionLists(min, that.min) // объединяем два корневых списка
size += that.size
'''if''' min <tex>= \varnothing</tex> '''or''' (that.min <tex> \neq \varnothing</tex> '''and''' that.min < min) // если минимум кучи изменился, то надо обновить указатель
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) // список детей min объединяем с корневым
'''Node''' L = min.left // аккуратно удаляем min из списка
'''Node''' R = min.right
L.right = R
R.left = L
'''if''' prevMin.right = prevMin // отдельно рассмотрим случай с одним элементом
min <tex>= \varnothing</tex>
'''return'''
min = min.right // пока что перекинем указаиель min на правого сына, а далее consolidate() скорректирует min в процессе выполнения
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 // создаем массив и инициализируем его min
'''Node''' current = min.right
'''while''' A[current.degree] <tex>\neq</tex> current // пока элементы массива меняются
'''if''' A[current.degree] <tex>= \varnothing</tex> // если ячейка пустая, то положим в нее текущий элемент
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
</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 // если после изменения структура дерева сохранится, то меняем и выходим
x.key = newValue
'''return'''
'''Node''' parent = x.parent // иначе вызываем cut и cascadingCut
cut(x)
cascadingCut(x.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 // аккуратно удаляем текущую вершину
L.right = R
x.right = x
x.left = x
x.parent.degree--
'''if''' x.parent.child = x // чтобы родитель не потерял ссылку на сыновей проверяем: 
'''if''' x.right = x. // если узел который мы вырезаем содержится в родителе, то меняем его на соседний
x.parent.child <tex>= \varnothing</tex> // иначе у родителя больше нет детей
'''else'''
x.parent.child = x.right
x.parent <tex>= \varnothing</tex>
unionLists(min, x) // вставляем наше поддерево в корневой список
</code>

===== Каскадное вырезание =====
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]
<code style="display:inline-block">
'''function''' cascadingCut(x: '''Node''')
'''while''' x.mark = '''true''' // пока у нас помеченые вершины вырезаем их
cut(x)
x = x.parent
x.mark = true // последнюю вершину нужно пометить {{---}} у нее удаляли ребенка
</code>

'''Пример'''

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

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

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

== Время работы ==
==== Потенциал ====
Для анализа производительности операций введем потенциал для фибоначчиевой кучи как <tex> \Phi = trees + 2 * marked </tex>, где <tex> trees </tex> {{---}} количество элементов в корневом списке кучи, а <tex> marked </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.
==== Cоздание кучи ====
Очевидно, что реальное время работы {{---}} <tex> O(1) </tex>.
==== Вставка элемента ====
Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> trees(H') = trees(H) + 1 </tex> и <tex> marked(H') = marked(H) </tex>. Следовательно, увеличение потенциала составляет <tex> (trees(H) + 1 + 2 * marked(H)) - (trees(H) + 2 * marked(H)) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.
==== Получение минимального элемента ====
Истинное время работы {{---}} <tex> O(1) </tex>.
==== Соедининение двух куч ====
Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.
==== Удаление минимального элемента====
Для доказательства времени работы этого алгоритма нам понадобится доказать несколько вспомогательных утверждений.
{{Лемма
|id=Лемма1
|statement=Для всех целых <tex> n \geqslant 2</tex>
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:
<tex>
F_n =
\begin{cases}
0, & n = 0 \\
1, & n = 1 \\
F_{n-1} + F_{n-2}, & n \geqslant 2
\end{cases} </tex>
|proof=
Докажем лемму по индукции:

при <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>. Тогда

<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>
}}

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

При <tex>n = 0</tex>

<tex>s_0 = 1 > F_0</tex>.

При <tex>n = 1</tex>

<tex>s_1 = 1 = F_1</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>

Но по предыдущей [[#Лемма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>n = 0</tex>

<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.

При <tex>n = 1</tex>

<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.

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

<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex>

<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex>

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

Поскольку <tex>\left\vert (-\varphi)^{-1} \right\vert < 1</tex>, то выполняются неравенства <tex dpi="160">\frac {(-\varphi)^{-n}} {\sqrt 5} < \frac {1} {\sqrt 5} < \frac {1} {2}</tex>. Таким образом, <tex>n</tex>-ое число Фибоначчи равно <tex dpi="160">\frac {\varphi^{n}} {\sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_n =O(\varphi^n)</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>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant k</tex>

Таким образом, максимальная степень <tex>degree</tex> произвольной вершины равна <tex>O(\log n)</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> 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(degree + trees) + (degree + 1 + 2 * marked) - (trees + 2 * marked) = O(degree) + O(trees) - trees</tex>

Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(degree) </tex>
==== Уменьшение значения элемента ====
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

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

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

В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((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>\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>
|}

== Недостатки и достоинства ==
'''Недостатки''':
* Большое потребление памяти на узел(минимум 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]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Приоритетные очереди]]

2-3 дерево

2017-01-31T08:58:11Z

92.242.59.6:

[[Файл:23treemain.png|400px|Пример 2-3 дерева|thumb]]''' 2-3 дерево '''(англ. ''2-3 tree'') — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]].
== Свойства ==
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
*нелистовые вершины имеют либо <tex>2</tex>, либо <tex>3</tex> сына,
*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
*сыновья упорядочены по значению максимума поддерева сына,
*все листья лежат на одной глубине,
*высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{---}} количество элементов в дереве.

== Операции ==
Введем следующие обозначения:
*<tex>\mathtt{root}</tex> {{---}} корень 2-3 дерева.
Каждый узел дерева обладает полями:
*<tex>\mathtt{parent}</tex> {{---}} родитель узла,
*<tex>\mathtt{sons}</tex> {{---}} сыновья узла,
*<tex>\mathtt{keys}</tex> {{---}} ключи узла,
*<tex>\mathtt{length}</tex> {{---}} количество сыновей.
=== Поиск ===
*<tex>x</tex> {{---}} искомое значение,
*<tex>t</tex> {{---}} текущая вершина в дереве.

Изначально <tex>t = \mathtt{root}</tex>. Будем просматривать ключи в узлах, пока узел не является листом. Рассмотрим два случая:
*у текущей вершины два сына. Если её значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.

*у текущей вершины три сына. Если второе значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[2]}</tex>. Если первое значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.

'''T''' search('''T''' x):
Node t = root
'''while''' (t не является листом)
'''if''' (t.length == 2)
'''if''' (t.keys[0] < x)
t = t.sons[1]
'''else'''
t = t.sons[0]
'''else''' '''if''' (t.keys[1] < x)
t = t.sons[2]
'''else''' '''if''' (t.keys[0] < x)
t = t.sons[1]
'''else'''
t = t.sons[0]
'''return''' t.keys[0]

[[Файл:23treesearch.png|thumb|center|600px|Поиск элемента 19, оранжевые стрелки обозначают путь по дереву при поиске]]

=== Вставка элемента ===
*<tex>x</tex> {{---}} добавляемое значение,
*<tex>t</tex> {{---}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.
Если корня не существует {{---}} дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:

Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.

Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя, ведь у него тоже могло быть уже <tex>3</tex> сына, а мы разделили и у него стало на <tex>1</tex> сына больше. (перед разделением обновим ключи).

'''function''' splitParent('''Node''' t):
'''if''' (t.length > 3)
Node a = Node(sons = {t.sons[2], t.sons[3]}, keys = {t.keys[2]}, parent = t.parent, length = 2)
t.sons[2].parent = a
t.sons[3].parent = a
t.length = 2
t.sons[2] = ''null''
t.sons[3] = ''null''
'''if''' (t.parent != ''null'')
t.parent[t.length] = a
t.length++
сортируем сыновей у t.parent
splitParent(t.parent)
'''else''' // мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем
Node t = root
root.sons[0] = t
root.sons[1] = a
t.parent = root
a.parent = root
root.length = 2
сортируем сыновей у root
Если сыновей стало <tex>3</tex>, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:
'''function''' updateKeys('''Node''' t):
Node a = t.parent
'''while''' (a != ''null'')
'''for''' i = 0 .. a.length - 1
a.keys[i] = max(a.sons[i]) // max {{---}} возвращает максимальное значение в поддереве.
a = a.parent // Примечание: max легко находить, если хранить максимум 
// правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])

<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
Добавление элемента:
'''function''' insert('''T''' x):
Node n = Node(x)
'''if''' (root == ''null'')
root = n
'''return'''
Node a = searchNode(x)
'''if''' (a.parent == ''null'')
Node t = root
root.sons[0] = t
root.sons[1] = n
t.parent = root
n.parent = root
root.length = 2
сортируем сыновей у root
'''else'''
Node p = a.parent
p.sons[p.length] = n
p.length++
n.parent = p
сортируем сыновей у p
updateKeys(n)
split(n)
updateKeys(n)
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.

Примеры добавления:

[[Файл:23treeinsert.png|thumb|center|Добавление элемента с ключом 6|600px]]

=== Удаление элемента ===
*<tex>x</tex> {{---}} значение удаляемого узла,
*<tex>t</tex> {{---}} текущий узел,
*<tex>b</tex> {{---}} брат <tex>t</tex>,
*<tex>p</tex> {{---}} отец <tex>t</tex>,
*<tex>np</tex> {{---}} соседний брат <tex>p</tex>,
*<tex>gp</tex> {{---}} отец <tex>p</tex>.
Пусть изначально <tex>t = \mathtt{searchNode(x)}</tex> {{---}} узел, где находится <tex>x</tex>.

Если у <tex>t</tex> не существует родителя, то это корень (одновременно и единственный элемент в дереве). Удалим его.

Если <tex>p</tex> существует, и у него строго больше <tex>2</tex> сыновей, то просто удалим <tex>t</tex>, а у <tex>p</tex> уменьшим количество детей.

Если у родителя <tex>t</tex> два сына, рассмотрим возможные случаи (сперва везде удаляем <tex>t</tex>):
*<tex>np</tex> не существует, тогда мы удаляем одного из сыновей корня, следовательно, другой сын становится новым корнем,
*у <tex>gp</tex> оказалось <tex>2</tex> сына, у <tex>np</tex> оказалось <tex>2</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>p</tex>. Так как у <tex>gp</tex> {{---}} родителя <tex>p</tex>, оказалось тоже два сына,повторяем для <tex>p</tex> такие же рассуждения,
*у <tex>gp</tex> оказалось <tex>2</tex> или <tex>3</tex> сына, у <tex>np</tex> оказалось <tex>3</tex> сына. Просто заберем ближайшего к нам сына у <tex>np</tex> и прицепим его к <tex>p</tex>. Восстановим порядок в сыновьях <tex>p</tex>. Теперь у <tex>p</tex> оказалось снова два сына и все узлы 2-3 дерева корректны,
*у <tex>gp</tex> оказалось <tex>3</tex> сына, у <tex>np</tex> оказалось <tex>2</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>p</tex>, а у <tex>gp</tex> уменьшим количество детей. Так как у <tex>np</tex> оказалось три сына, а у <tex>gp</tex> все ещё больше одного сына, то все узлы 2-3 дерева корректны.

Обобщим алгоритм при удалении когда у родителя <tex>t</tex> два сына:
*Если <tex>np</tex> не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.

*Если <tex>np</tex> существует, то удалим <tex>t</tex>, а его брата (<tex>b</tex>) перецепим к <tex>np</tex>. Теперь у <tex>np</tex> могло оказаться <tex>4</tex> сына, поэтому повторим аналогичные действия из <tex>\mathtt{insert}</tex>: вызовем <tex>\mathtt{updateKeys}(b)</tex> и <tex>\mathtt{splitParent}(np)</tex>. Теперь рекурсивно удалим <tex>p</tex>.

В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>.
[[Файл:23treedelete.png|thumb|center|Удаление элемента с ключом 2|1150px]]

=== Следующий и предыдущий ===
*<tex>x</tex> {{---}} поисковый параметр,
*<tex>t</tex> {{---}} текущий узел.
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект {{---}} это соседний лист справа. Попасть туда можно следующим образом:
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
'''T''' next('''T''' x):
Node t = searchNode(x)
'''if''' (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу
'''return''' t.keys[0]
'''while''' (t != ''null'')
t = t.parent
'''if''' (можно свернуть направо вниз)
в t помещаем вершину, в которую свернули
'''while''' (пока t {{---}} не лист)
t = t.sons[0]
'''return''' t
'''return''' t.keys[0]

[[Файл:23treenext.png|thumb|center|400px|Путь при поиске следующего элемента после 2]]

=== Нахождение m следующих элементов ===
B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом: будем вызывать <tex>m</tex> раз поиск следующего элемента, такое решение работает за <tex>O(m \log{n})</tex>. Но 2-3 деревья, позволяют находить m следующих элементов за <tex>O(m + \log{n})</tex>, что значительно ускоряет поиск при больших <tex>m</tex>.
По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем
<tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля:
*<tex>\mathtt{right}</tex> {{---}} указывает на правый лист,
*<tex>\mathtt{left}</tex> {{---}} указывает на левый лист.
Пусть <tex>t</tex> {{---}} добавленный узел.
Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом конце, после того как мы уже обновили все ключи, найдем <tex>\mathtt{next(t)}</tex> и запишем ссылку на него в <tex>\mathtt{t.right}</tex>. Аналогично с левым.

Пусть <tex>t</tex> {{---}} удаляемый узел. Изменим <tex>\mathtt{delete}</tex> следующим образом: в самом начале, до удаления <tex>t</tex>, найдем следующий <tex>\mathtt{next}</tex> и запишем в <tex>\mathtt{next.left}</tex> правый лист относительно <tex>t</tex>. С левым поступим аналогично.

В итоге, мы имеем двусвязный список в листьях, и чтобы нам вывести <tex>m</tex> элементов, нам достаточно один раз найти нужный элемент и пробежаться вправо на <tex>m</tex> элементов.

[[Файл:23treefindm.png|thumb|Изменение ссылок при добавлении нового элемента|thumb|center|800px]]

== См. также ==
* [[B-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
* [[Декартово дерево]]
* [[Красно-черное дерево]]

== Источники информации ==
* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.ifmo.ru {{---}} Визуализатор 2-3 дерева]
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru {{---}} Визуализатор 2-3 дерева]
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия {{---}} 2-3 дерево]
* Д. Кнут «Искусство программирования. Сортировка и поиск» {{---}} стр. 508-509

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Структуры данных]]
[[Категория:Деревья поиска]]