Куча Фибоначчи

Куча Фибоначчи
Тип	куча
Изобретенный	1984
Изобретён	Майкл Л. Фредман и Роберт Э. Тарджан
Сложности в обозначении большого О
Пространственная сложность Временная сложность Функция Амортизированный Худший случай Вставлять я (1) Найти-мин я (1) Удалить-мин. О(логарифм n ) Клавиша уменьшения я (1) Объединить я (1)

В информатике куча Фибоначчи — это структура данных для операций очереди с приоритетом , состоящая из набора упорядоченных по куче деревьев . Он имеет лучшее амортизированное время работы, чем многие другие структуры данных очереди приоритетов, включая двоичную и биномиальную кучу . Майкл Л. Фредман и Роберт Э. Тарьян разработали кучи Фибоначчи в 1984 году и опубликовали их в научном журнале в 1987 году. Кучи Фибоначчи названы в честь чисел Фибоначчи , которые используются в их анализе времени выполнения.

Амортизированное время всех операций с кучей Фибоначчи является постоянным, за исключением delete-min . Удаление элемента (чаще всего используется в частном случае удаления минимального элемента) работает в $O(\log n)$ амортизированное время, где $n$ это размер кучи. Это означает, что, начиная с пустой структуры данных, любая последовательность операций вставки и уменьшения клавиш , а также b операций удаления минимального значения будет занимать $O(a+b\log n)$ время наихудшего случая, когда $n$ — максимальный размер кучи. В двоичной или биномиальной куче такая последовательность операций заняла бы $O((a+b)\log n)$ время. Таким образом, куча Фибоначчи лучше, чем двоичная или биномиальная куча, когда $b$ меньше, чем $a$ непостоянным фактором. Также возможно объединить две кучи Фибоначчи за постоянное амортизированное время, улучшив время логарифмического слияния биномиальной кучи и улучшив двоичные кучи, которые не могут эффективно обрабатывать слияния.

Использование куч Фибоначчи улучшает асимптотическое время работы алгоритмов, использующих очереди с приоритетами. Например, алгоритм Дейкстры и алгоритм Прима можно запустить в $O(|E|+|V|\log |V|)$ время.

Структура

Рисунок 1. Пример кучи Фибоначчи. Он имеет три дерева степеней 0, 1 и 3. Отмечены три вершины (показаны синим цветом). Следовательно, потенциал кучи равен 9 (3 дерева + 2 × (3 помеченных вершины)).

Куча Фибоначчи — это совокупность деревьев, удовлетворяющих свойству минимальной кучи , то есть ключ дочернего элемента всегда больше или равен ключу родительского элемента. Это означает, что минимальный ключ всегда находится в корне одного из деревьев. По сравнению с биномиальными кучами структура кучи Фибоначчи более гибкая. Деревья не имеют заданной формы, и в крайнем случае куча может содержать каждый элемент в отдельном дереве. Эта гибкость позволяет выполнять некоторые операции ленивым образом, откладывая работу для последующих операций. Например, объединение куч осуществляется просто путем объединения двух списков деревьев, а операция уменьшения ключа иногда отсекает узел от его родителя и формирует новое дерево.

Однако в какой-то момент для достижения желаемого времени работы в куче необходимо навести порядок. В частности, степени узлов (здесь степень означает количество прямых потомков) сохраняются довольно низкими: каждый узел имеет не более степени. $\log n$ и размер поддерева с корнем в узле степени $k$ по крайней мере $F_{k+2}$, где $F_{i}$ это $i$число Фибоначчи . Это достигается правилом: от каждого некорневого узла можно отрезать не более одного дочернего узла. Когда второй дочерний элемент вырезается, сам узел должен быть отрезан от своего родителя и становится корнем нового дерева (см. «Доказательство границ степени» ниже). Количество деревьев уменьшается в операции delete-min , где деревья связаны друг с другом.

В результате расслабленной структуры некоторые операции могут занимать много времени, а другие выполняются очень быстро. Для анализа амортизированного времени выполнения мы используем потенциальный метод , в котором мы делаем вид, что очень быстрые операции занимают немного больше времени, чем на самом деле. Это дополнительное время затем суммируется и вычитается из фактического времени выполнения медленных операций. Количество времени, сэкономленное для последующего использования, измеряется в любой момент потенциальной функцией. Потенциал $\phi$ кучи Фибоначчи определяется выражением

$\phi =t+2m$,

где $t$ - количество деревьев в куче Фибоначчи, а $m$ — количество отмеченных узлов. Узел помечается, если хотя бы один из его дочерних узлов был вырезан, поскольку этот узел был сделан дочерним по отношению к другому узлу (все корни не отмечены). Амортизированное время операции определяется как сумма фактического времени и $c$ раз на разницу потенциалов, где c — константа (выбранная для соответствия постоянным коэффициентам в большом обозначении O для фактического времени).

Таким образом, в корне каждого дерева в куче хранится одна единица времени. Эту единицу времени можно использовать позже для связи этого дерева с другим деревом в амортизированное время 0. Кроме того, в каждом отмеченном узле хранятся две единицы времени. Один из них можно использовать для отделения узла от его родителя. Если это произойдет, узел станет корнем и вторая единица времени останется сохраненной в нем, как и в любом другом корне.

Операции

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

Найти-мин

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

идти

Операция слияния просто объединяет корневые списки двух куч и устанавливает минимальный из двух куч. Это можно сделать за постоянное время, и потенциал не изменится, что снова приведет к постоянному амортизированному времени.

Вставить

Операцию вставки можно рассматривать как частный случай операции слияния с одним узлом. Узел просто добавляется в корневой список, увеличивая потенциал на единицу. Таким образом, амортизированная стоимость остается постоянной.

Удалить-мин

Рисунок 2. Первая фаза delete-min .

Рисунок 3. Третья фаза delete-min .

Операция delete-min выполняет большую часть работы по восстановлению структуры кучи. Он имеет три фазы:

1. Корень, содержащий минимальный элемент, удаляется, и каждый его элемент $d$ дети становятся новым корнем. Это требует времени $O(d)$ обработать эти новые корни, и потенциал увеличивается на $d-1$. Следовательно, амортизированное время выполнения этой фазы равно $O(d)=O(\log n)$.
2. Может быть до $n$ корни. Поэтому мы уменьшаем число корней, последовательно соединяя корни одной степени. Когда два корня имеют одинаковую степень, мы делаем тот, у которого ключ большего размера, дочерним по отношению к другому, чтобы соблюдалось свойство минимальной кучи. Степень меньшего корня увеличивается на единицу. Это повторяется до тех пор, пока каждый корень не будет иметь разную степень. Чтобы эффективно находить деревья одной степени, мы используем массив длины $O(\log n)$ в котором мы храним указатель на один корень каждой степени. Когда обнаруживается второй корень той же степени, они связываются, и массив обновляется. Фактическое время работы $O(\log n+m)$, где $m$ – число корней в начале второй фазы. В итоге мы получим максимум $O(\log n)$ корни (потому что каждый имеет разную степень). Следовательно, разница потенциалов до и после этой фазы равна $O(\log n)-m$. Таким образом, амортизированное время работы равно $O(\log n+m)+c(O(\log n)-m)$. Выбрав достаточно большое $c$ такие, что условия в $m$ отменить, это упрощает $O(\log n)$.
3. Найдите окончательный список корней, чтобы найти минимум, и соответствующим образом обновите указатель минимума. Это занимает $O(\log n)$ время, потому что количество корней уменьшилось.

В целом амортизированное время этой операции составляет $O(\log n)$, при условии, что $d=O(\log n)$. Доказательство этого приведено в следующем разделе.

Клавиша уменьшения

Рисунок 4. Куча Фибоначчи с рисунка 1 после уменьшения ключа узла 9 до 0.

Если уменьшить ключ узла $x$ заставляет его становиться меньше своего родителя, затем он отсекается от своего родителя, становясь новым немаркированным корнем. Если он также меньше минимального ключа, то минимальный указатель обновляется.

Затем мы инициируем серию каскадных сокращений , начиная с родительского элемента. $x$. Пока текущий узел помечен, он отсекается от своего родителя и становится немаркированным корнем. Затем рассматривается его первоначальный родитель. Этот процесс останавливается, когда мы достигаем немаркированного узла. $y$. Если $y$ не является корнем, он помечен. В этом процессе мы вводим некоторое число, скажем $k$, новых деревьев. За исключением, возможно, $x$, каждое из этих новых деревьев теряет свою первоначальную метку. Конечный узел $y$ может стать отмеченным. Следовательно, изменение количества отмеченных узлов происходит между $-k$ и $-k+2$. Результирующее изменение потенциала $k+2(-k+2)=-k+4$. Фактическое время, необходимое для выполнения резки, составило $O(k)$. Следовательно, амортизированное время $O(k)+c(-k+4)$, который является постоянным при условии $c$ достаточно велик.

Доказательство границ степени

Амортизированная производительность кучи Фибоначчи зависит от степени (количества дочерних элементов) любого корня дерева. $O(\log n)$, где $n$ это размер кучи. Здесь мы показываем, что размер (под)дерева с корнем в любом узле $x$ степени $d$ в куче должен быть размер не менее $F_{d+2}$, где $F_{i}$ это $i$число Фибоначчи . Оценка степени следует из этого и того факта (легко доказываемого по индукции), что $F_{d+2}\geq \varphi ^{d}$ для всех целых чисел $d\geq 0$, где $\varphi =(1+{\sqrt {5}})/2\approx 1.618$ это золотое сечение . Тогда у нас есть $n\geq F_{d+2}\geq \varphi ^{d}$, и переносим лог в базу $\varphi$ обеих сторон дает $d\leq \log _{\varphi }n$ по мере необходимости.

Позволять $x$ быть произвольным узлом в куче Фибоначчи, не обязательно корнем. Определять $\mathrm {size} (x)$ быть размером с дерево, у которого корни $x$ (число потомков $x$, включая $x$ сам). Докажем индукцией по высоте $x$ (длина самого длинного пути от $x$ до листа-потомка), что $\mathrm {size} (x)\geq F_{d+2}$, где $d$ это степень $x$.

Базовый случай: если $x$ имеет высоту $0$, затем $d=0$, и $\mathrm {size} (x)=1\geq F_{2}$.

Индуктивный случай: предположим $x$ имеет положительную высоту и степень $d>0$. Позволять $y_{1},y_{2}\dots y_{d}$ быть детьми $x$, проиндексированные в порядке времени, когда они в последний раз стали детьми $x$ ( $y_{1}$ являющийся самым ранним и $y_{d}$ самое последнее), и пусть $c_{1},c_{2}\dots c_{d}$ быть их соответствующими степенями.

Мы утверждаем, что $c_{i}\geq i-2$ для каждого $i$. незадолго до $y_{i}$ был сделан ребенком $x$, $y_{1}\dots y_{i-1}$ уже были детьми $x$, и так $x$ должен был иметь как минимум степень $i-1$ в это время. Поскольку деревья объединяются только тогда, когда степени их корней равны, должно было быть так, что $y_{i}$ тоже имел степень как минимум $i-1$ в то время, когда он стал ребенком $x$. С того времени и по настоящее время $y_{i}$ мог потерять не более одного ребенка (что гарантировано процессом маркировки), и поэтому его текущая степень $c_{i}$ по крайней мере $i-2$. Это доказывает утверждение.

Поскольку высоты всех $y_{i}$ строго меньше, чем у $x$, мы можем применить к ним индуктивную гипотезу, чтобы получить

$$\mathrm {size} (y_{i})\geq F_{c_{i}+2}\geq F_{(i-2)+2}=F_{i}.$$

Узлы $x$ и $y_{1}$ каждый вносит минимум 1 в $\mathrm {size} (x)$и так у нас есть

$${\begin{aligned}\mathrm {size} (x)&\geq 2+\sum _{i=2}^{d}\mathrm {size} (y_{i})\\&\geq 2+\sum _{i=2}^{d}F_{i}\\&=1+\sum _{i=0}^{d}F_{i}\\&=F_{d+2}\end{aligned}}$$

где последний шаг — это тождество чисел Фибоначчи. Это дает желаемую нижнюю границу $\mathrm {size} (x)$.

Производительность

Хотя кучи Фибоначчи выглядят очень эффективно, у них есть два недостатка:

1. Они сложны в реализации.
2. На практике они не так эффективны по сравнению с теоретически менее эффективными формами куч. , требуются только два или три указателя на узел В своей простейшей версии они требуют манипулирования четырьмя указателями на узел, тогда как в других структурах, таких как биномиальная куча или парная куча . Это приводит к большому потреблению памяти на узел и высоким постоянным коэффициентам для всех операций.

Хотя общее время выполнения последовательности операций, начинающихся с пустой структуры, ограничено пределами, указанными выше, некоторые (очень немногие) операции в последовательности могут занять очень много времени (в частности, delete-min имеет линейное время выполнения в худший случай). По этой причине кучи Фибоначчи и другие амортизированные структуры данных могут не подходить для систем реального времени .

Можно создать структуру данных, которая будет иметь такую ​​же производительность в худшем случае, как амортизированная производительность кучи Фибоначчи. Одна из таких структур — очередь Бродала . является, по словам создателя, «достаточно сложным» и «[не]применимо на практике». , изобретенная в 2012 году. Строгая куча Фибоначчи является более простой (по сравнению со структурой Бродала) структурой с теми же границами наихудшего случая. Несмотря на свою простоту, эксперименты показывают, что на практике строгая куча Фибоначчи работает медленнее, чем более сложная очередь Бродала , а также медленнее, чем базовая куча Фибоначчи. Расслабленные от бега кучи Driscoll et al. обеспечивают хорошую производительность в худшем случае для всех операций с кучей Фибоначчи, кроме слияния. Недавние экспериментальные результаты показывают, что куча Фибоначчи на практике более эффективна, чем большинство ее более поздних производных, включая кучи землетрясений, кучи нарушений, строгие кучи Фибоначчи и кучи спаривания рангов, но менее эффективна, чем кучи спаривания или кучи на основе массивов.

Сводка времени работы

Вот временные сложности различных структур данных кучи. Имена функций предполагают минимальную кучу. Значение « O ( f )» и « Θ ( f )» см в обозначении Big O. .

Операция	найти-мин	удаление-мин	вставлять	клавиша уменьшения	сливаться
Двоичный	я (1)	Θ (логарифм n )	О (логарифм n )	О (логарифм n )	Θ ( н )
Левый	я (1)	Θ (логарифм n )	Θ (логарифм n )	О (логарифм n )	Θ (логарифм n )
Биномиальный	я (1)	Θ (логарифм n )	я (1)	Θ (логарифм n )	О (логарифм n )
Наклонный бином	я (1)	Θ (логарифм n )	я (1)	Θ (логарифм n )	О (логарифм n )
Сопряжение	я (1)	О (логарифм n )	я (1)	о (логарифм n )	я (1)
Сопряжение по рангам	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
Фибоначчи	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
Строгий Фибоначчи	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
Мостовая долина	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
2–3 кучи	я (1)	О (логарифм n )	я (1)	я (1)	О (логарифм n )

Внешние ссылки

• Java-апплет, симулирующий кучу Фибоначчи
• MATLAB реализация кучи Фибоначчи
• Дерекурсивная и эффективная по использованию памяти реализация кучи Фибоначчи на языке C (бесплатное/бесплатное программное обеспечение, лицензия CeCILL-B )
• Ruby-реализация кучи Фибоначчи (с тестами)
• Псевдокод алгоритма кучи Фибоначчи