Куча Фибоначчи - Fibonacci heap

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

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

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

Состав

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

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

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

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

Потенциал = t + 2 м

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

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

Осуществление операций

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

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

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

Операция 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 ) амортизированное время работы является постоянным.

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

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

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

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

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

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

Поскольку высоты всех y _i строго меньше высоты x , мы можем применить к ним индуктивную гипотезу, чтобы получить size ( y _i ) ≥  F _{c i +2}  ≥  F _{( i −2) +2}  =  F _i . Каждый из узлов x и y ₁ вносит по крайней мере 1 в размер ( x ), поэтому мы имеем

${\ 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}.}$

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

Худший случай

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

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

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

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

Вот временные сложности различных структур данных кучи. Имена функций предполагают минимальную кучу. Для значения " O ( F )" и " thetas ; ( е )" см Big O нотацию .

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

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

Рекомендации

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

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