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

Материал из Викиконспекты
Перейти к: навигация, поиск

Содержание

[править] Фибоначчиево дерево

Определение:
Фибоначчиево дерево (англ. Fibonacci tree) — биномиальное дерево, где у каждой вершины удалено не более одного ребенка.


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


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


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

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

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

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

при n = 2

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

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

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

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

При n = 0

s_0 = 1 > F_0.

При n = 1

s_1 = 1 = F_1.

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

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

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

1 + \sum\limits_{i=0}^{n-2} F_i = F_n. Следовательно, s_n \geqslant F_n
\triangleleft

[править] Фибоначчиева куча

Определение:
Фибоначчиева куча (англ. Fibonacci heap) — набор фибоначчиевых деревьев, корни которых объединены в неупорядоченный циклический двусвязный список. В отличие от биномиальной кучи, степени корней не обязаны быть попарно различными.

Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1).

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

Лемма:
F_n =\Theta(\varphi^n), где \varphi = \frac {1 + \sqrt 5} {2}
Доказательство:
\triangleright

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

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

При n = 0

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

При n = 1

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

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

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

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

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

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


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

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

n \geqslant \varphi^{k}

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

\log_{\varphi}n \geqslant k

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

[править] Структура

[править] Структура узла

Каждый узел x в куче H содержит следующие указатели и поля:

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

[править] Структура кучи

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

[править] Структура списка детей

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

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

[править] Потенциал

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

[править] Операции

Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.

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


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

[править] makeHeap

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

[править] insert

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

[править] getMin

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

[править] merge

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

[править] extractMin

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

[править] consolidate

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

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

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

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

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

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

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

[править] decreaseKey

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

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

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

[править] cascadingCut
Пример каскадного вырезания

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

Пример

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

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

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

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

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

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

[править] delete

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

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

[править] См. также

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты