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

редактировать

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

Тип

куча

Изобретено

1984

Изобретено

Майкл Л. Фредман и Роберт Эндре Тарджан

Сложность времени в нотации большого O

Алгоритм	Среднее	Худший случай
Вставить	Θ ( 1)
Find-min	Θ (1)
Delete-min	O (log n)
Клавиша уменьшения	Θ (1)
Объединить	Θ (1)

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

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

Использование кучи Фибоначчи для очередей с приоритетом улучшает асимптотическое время работы важных алгоритмов, таких как алгоритм Дейкстры для вычисления кратчайшего пути между двумя узлами в графе, по сравнению к тому же алгоритму с использованием других структур данных очереди с более медленным приоритетом.

Содержание

1 Структура
2 Реализация операций
3 Подтверждение границ степеней
4 Худший случай
5 Сводка времени выполнения
6 Практические соображения
7 Ссылки
8 Внешние ссылки

Структура

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

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

Однако в какой-то момент необходимо внести в кучу порядок, чтобы достичь желаемого времени работы. В частности, степени узлов (здесь степень означает количество прямых дочерних узлов) сохраняются довольно низкими: каждый узел имеет степень не выше O (log n), а размер поддерева, основанного на узле степени k, не менее F k + 2, где F k - k-е число Фибоначчи. Это достигается правилом, согласно которому мы можем вырезать не более одного дочернего элемента каждого некорневого узла. Когда второй дочерний элемент вырезается, сам узел должен быть отрезан от своего родителя и становится корнем нового дерева (см. Доказательство границ степеней ниже). Количество деревьев уменьшается в операции удаления минимум, когда деревья связаны между собой.

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

Potential = t + 2m

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

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

Реализация операций

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

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

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

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

Операция извлечь минимум (то же самое, что удалить минимум) работает в три этапа. Сначала мы берем корень, содержащий минимальный элемент, и удаляем его. Его дети станут корнями новых деревьев. Если количество дочерних элементов было d, требуется время O (d) для обработки всех новых корней, и потенциал увеличивается на d − 1. Следовательно, амортизированное время работы этой фазы составляет O (d) = O (log n).

Однако для завершения минимальной операции извлечения нам нужно обновить указатель на корень с минимальным ключом. К сожалению, нам может потребоваться проверить до n корней. Поэтому на втором этапе мы уменьшаем количество корней, последовательно соединяя вместе корни одинаковой степени. Когда два корня u и v имеют одинаковую степень, мы делаем один из них дочерним по отношению к другому, так что корень с меньшим ключом остается. Его степень увеличится на единицу. Это повторяется до тех пор, пока каждый корень не будет иметь разную степень. Чтобы эффективно находить деревья одинаковой степени, мы используем массив длины O (log n), в котором мы храним указатель на один корень каждой степени. Когда обнаруживается второй корень той же степени, они связываются, и массив обновляется. Фактическое время работы составляет O (log n + m), где m - количество корней в начале второй фазы. В конце у нас будет не более O (log n) корней (потому что каждый имеет разную степень). Следовательно, разница в потенциальной функции до этой фазы и после нее составляет: O (log n) - m, а амортизированное время работы тогда не превосходит O (log n + m) + c (O (log n) - м). При достаточно большом выборе c это упрощается до O (log n).

Рисунок 2. Куча Фибоначчи с рисунка 1 после первой фазы извлечения минимума. Узел с ключом 1 (минимум) был удален, а его дочерние элементы были добавлены как отдельные деревья.

Рисунок 3. Куча Фибоначчи с рисунка 1 после завершения извлечения минимума. Сначала соединяются узлы 3 и 6. Затем результат связывается с деревом с корнем в узле 2. Наконец, новый минимум найден.

Рисунок 4. Куча Фибоначчи с рисунка 1 после уменьшения ключа узла 9 до 0. Этот узел, а также два его отмеченных предка являются вырезать из дерева с корнем 1 и поместить его как новые корни.

На третьем этапе мы проверяем каждый из оставшихся корней и находим минимум. Это занимает O (log n) времени, и потенциал не меняется. Таким образом, общее амортизированное время работы экстракта составляет O (log n).

Операция клавиша уменьшения возьмет узел, уменьшит ключ, и если свойство кучи нарушится (новый ключ меньше, чем ключ родителя), узел будет вырезан из его родитель. Если родитель не является корнем, он помечается. Если он уже был отмечен, он также будет вырезан, и его родительский элемент будет отмечен. Мы продолжаем движение вверх, пока не дойдем до корневого или немаркированного узла. Теперь мы устанавливаем указатель минимума на уменьшенное значение, если это новый минимум. В процессе мы создаем некоторое количество, скажем k, новых деревьев. Каждое из этих новых деревьев, кроме, возможно, первого, было изначально помечено, но как корень оно станет немаркированным. Можно отметить один узел. Следовательно, количество отмеченных узлов изменяется на - (k - 1) + 1 = - k + 2. Объединяя эти 2 изменения, потенциал изменяется на 2 (−k + 2) + k = −k + 4. Фактическое время для выполнения резания было O (k), поэтому (опять же при достаточно большом выборе c) амортизированное время работы постоянно.

Наконец, операцию delete можно реализовать, просто уменьшив ключ удаляемого элемента до минус бесконечности, таким образом превратив его в минимум всей кучи. Затем мы вызываем минимум извлечения, чтобы удалить его. Амортизированное время выполнения этой операции составляет O (log n).

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

Амортизированная производительность кучи Фибоначчи зависит от степени (количества дочерних элементов) того, что корень любого дерева равен O (log n), где n - размер куча. Здесь мы показываем, что размер (под) дерева с корнем в любом узле x степени d в куче должен иметь размер не менее F d+2, где F k - k-е число Фибоначчи.. Граница степени следует из этого и того факта (легко доказываемого по индукции), что $F d + 2 ≥ φ d {\ displaystyle F_ {d + 2} \ geq \ varphi ^ {d}}$ $F_ {d + 2} \ geq \ varphi ^ {d}$ для всех целых чисел $d ≥ 0 {\ displaystyle d \ geq 0}$ $d \ geq 0$ , где $φ = (1 + 5) / 2 ≐ 1.618 {\ displaystyle \ varphi = (1 + {\ sqrt {5}}) / 2 \ doteq 1.618}$ $\ varphi = (1 + {\ sqrt {5}}) / 2 \ doteq 1.618$ . (Затем у нас есть $n ≥ F d + 2 ≥ φ d {\ displaystyle n \ geq F_ {d + 2} \ geq \ varphi ^ {d}}$ $n \ geq F_ {d + 2} \ geq \ varphi ^ {d}$ , и беря журнал на основание $φ {\ displaystyle \ varphi}$ $\ varphi$ с обеих сторон дает $d ≤ log φ ⁡ n {\ displaystyle d \ leq \ log _ {\ varphi} n}$ $d \ leq \ log _ {\ varphi} n$ как требуется.)

Рассмотрим любой узел x где-нибудь в куче (x не обязательно должен быть корнем одного из основных деревьев). Определите size (x) как размер дерева с корнем в x (количество потомков x, включая сам x). Мы докажем индукцией по высоте x (длине самого длинного простого пути от x до дочернего листа), что size (x) ≥ F d+2, где d - степень x.

Базовый случай: Если x имеет высоту 0, то d = 0 и size (x) = 1 = F 2.

Индуктивный случай: Предположим, что x имеет положительную высоту и степень d>0. Пусть y 1, y 2,..., y d будут потомками x, индексированными в порядке времени, когда они в последний раз были сделаны потомками x (y 1 является самым ранним, а y d самым последним), и пусть c 1, c 2,..., c d - их соответствующие степени. Мы утверждаем, что c i ≥ i-2 для каждого i с 2 ≤ i ≤ d: Незадолго до того, как y i стал потомком x, y 1,..., y i−1уже были потомками x, и поэтому x имел степень не менее i − 1 в то время. Поскольку деревья объединяются только тогда, когда степени их корней равны, должно быть, y i также имел степень не менее i-1 в то время, когда оно стало потомком x. С того времени и по настоящее время y i может потерять не более одного дочернего элемента (как гарантируется процессом маркировки), поэтому его текущая степень c i составляет не менее i− 2. Это доказывает утверждение .

Поскольку высоты всех y i строго меньше высоты x, мы можем применить к ним индуктивную гипотезу, чтобы получить size (yi) ≥ F ci+2≥ F (i − 2) +2 = F i. Узлы x и y 1 каждый вносят по крайней мере 1 в size (x), поэтому мы имеем

$size (x) ≥ 2 + ∑ i = 2 d size ( yi) ≥ 2 + ∑ i = 2 d F i = 1 + ∑ i = 0 d F i. {\ displaystyle {\ textbf {size}} (x) \ geq 2+ \ sum _ {i = 2} ^ {d} {\ textbf {size}} (y_ {i}) \ geq 2+ \ sum _ { i = 2} ^ {d} F_ {i} = 1 + \ sum _ {i = 0} ^ {d} F_ {i}.}$ ${\ textbf {size}} (x) \ geq 2+ \ sum _ {i = 2} ^ {d} {\ textbf {size}} (y_ {i}) \ geq 2+ \ sum _ {i = 2} ^ {d} F_ {i} = 1 + \ sum _ {i = 0} ^ {d} F_ {i}.$

Обычная индукция доказывает, что $1 + ∑ i = 0 d F я знак равно F d + 2 {\ displaystyle 1+ \ sum _ {i = 0} ^ {d} F_ {i} = F_ {d + 2}}$ $1+ \ sum _ {i = 0} ^ {d} F_ {i} = F_ {d + 2}$ для любого $d ≥ 0 {\ displaystyle d \ geq 0}$ $d \ geq 0$ , что дает желаемую нижнюю границу для size (x).

Наихудший случай

Хотя кучи Фибоначчи выглядят очень эффективно, у них есть два следующих недостатка (как упоминалось в статье «Сопряжение кучи: новая форма самонастраивающейся кучи»): «Они сложны, когда дело доходит до их кодирования. Кроме того, они не так эффективны на практике по сравнению с теоретически менее эффективными формами куч, поскольку в их простейшей версии они требуют хранения и манипулирования четырьмя указателями на узел по сравнению с двумя или тремя указатели на узел, необходимые для других структур ». Эти другие структуры называются двоичной кучей, двоичной кучей, парной кучей, кучей Бродала и кучей сопряжения рангов.

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

Сводка времени выполнения

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

Operation	find-min	delete-min	вставить	кнопка уменьшения	объединение
двоичное	Θ (1)	Θ (log n)	O (log n)	O (log n)	Θ (n)
Левый	Θ (1)	Θ (log n)	Θ (log n)	O (log n)	Θ (log n)
Биномиальный	Θ (1)	Θ (log n)	Θ(1)	Θ (log n)	O (log n)
Фибоначчи	Θ (1)	O (log n)	Θ (1)	Θ(1)	Θ (1)
Сопряжение	Θ (1)	O (log n)	Θ (1)	o (log n)	Θ (1)
Brodal	Θ (1)	O (log n)	Θ (1)	Θ (1)	Θ (1)
	Θ (1)	O (log n)	Θ (1)	Θ(1)	Θ (1)
Строгий Фибоначчи	Θ (1)	O (журнал n)	Θ (1)	Θ (1)	Θ (1)
2-3 куча	O (log n)	O (log n)	O (log n)	Θ (1)	?

Практические соображения

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

Ссылки

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