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

Фибоначчиево дерево

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

Фибоначчиево дерево — биномиальное дерево, где у каждой вершины удалено не более одного ребенка.

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

Порядок фибоначчиева дерева — порядок соответствующего биномиального дерева, из которого оно получено.

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

Степень вершины — количество дочерних узлов данной вершины.

Лемма:

Для всех целых [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]O(1)[/math].

С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций [math]\mathrm {extractMin}[/math] и [math]\mathrm {delete}[/math] относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные бинарные кучи.

Лемма:

[math]F_n =\Theta(\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 =\Theta(\varphi^n)[/math].

[math]\triangleleft[/math]

Лемма:

Максимальная степень [math]D(n)[/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]\Theta(\varphi^k)[/math]. То есть [math]n \geqslant \varphi^{k}[/math] Логарифмируя по основанию [math]\varphi[/math], получаем [math]\log_{\varphi}n \geqslant k[/math] Таким образом, максимальная степень [math]D(n)[/math] произвольной вершины равна [math]O(\log n)[/math].

[math]\triangleleft[/math]

Структура

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

• Каждый узел [math]x[/math] в куче [math]H[/math] содержит следующие указатели и поля:
  • [math]x.key[/math] — поле, в котором хранится ключ;
  • [math]x.p[/math] — указатель на родительский узел;
  • [math]x.child[/math] — указатель на один из дочерних узлов;
  • [math]x.left[/math] — указатель на левый сестринский узел;
  • [math]x.right[/math] — указатель на правый сестринский узел;
  • [math]x.degree[/math] — поле, в котором хранится количество дочерних узлов;
  • [math]x.mark[/math] — логическое значение, которое показывает, удаляли ли мы дочерние узлы данной вершины.
• Дочерние узлы [math]x[/math] объединены при помощи указателей [math]left[/math] и [math]right[/math] в циклический двусвязный список.
• Корни всех деревьев в [math]H[/math] связаны при помощи указателей [math]left[/math] и [math]right[/math] в циклический двусвязный список корней.
• Обращение к [math]H[/math] выполняется посредством указателя [math]H.min[/math] на корень дерева с минимальным ключом. Этот узел называется минимальным узлом [math]H[/math].
• Текущее количество узлов в [math]H[/math] хранится в [math]H.size[/math].

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

Потенциал

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

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

makeHeap

Создается новый пустой корневой список, в [math] H.min [/math] устанавливается значение [math] null [/math]. Реальное время работы — [math] O(1) [/math].

insert

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

getMin

Возвращает указатель [math]H.min[/math]. Реальное время работы — [math] O(1) [/math].

merge

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

extractMin

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

consolidate

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

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

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

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

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

[math] O(D(n) + t[H]) + (D(n) + 1 + 2m[H]) - (t[H] + 2m[H]) = O(D(n)) + O(t[H]) - t[H][/math]

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

decreaseKey

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

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

cut

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

cascadingCut

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

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

Пример

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

• Изначально, куча состояла из [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] \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} = ((t[H] + k) + 2(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k [/math]. Следовательно, амортизированная стоимость не превышает [math] O(k) + 4 - k [/math]. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции [math] \mathrm {decreaseKey} [/math] равна [math] O(1) [/math].

delete

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

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

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

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