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

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

Для кучи Фибоначчи операция поиска минимума занимает постоянное ( O (1)) амортизированное время. [1] Клавиши вставки и уменьшения также работают с постоянным амортизированным временем. [2] Удаление элемента (чаще всего используется в частном случае удаления минимального элемента) работает в течение O (log n ) амортизированного времени, где n - размер кучи. [2] Это означает , что , начиная с пустой структуры данных, любую последовательность на вставке и уменьшить ключевые операции и б операции удаления будет принимать O (  +  б  лог  н) время наихудшего случая, где n - максимальный размер кучи. В двоичной или биномиальной куче такая последовательность операций займет время 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 (журнал п ) - т ). При достаточно большом выборе 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- е число Фибоначчи . Оценка степени следует из этого и того факта (легко доказываемого по индукции), что для всех целых чисел , где . (Тогда мы имеем , и если положить бревно к основанию с обеих сторон, как требуется.)

Рассмотрим любой узел x где-нибудь в куче ( x не обязательно должен быть корнем одного из основных деревьев). Определите размер ( 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 ( y i ) ≥  F c i +2  ≥  F ( i −2) +2  =  F i . Каждый из узлов x и y 1 вносит как минимум 1 в размер ( x ), поэтому мы имеем

Обычная индукция доказывает это для любого , что дает желаемую нижнюю границу размера ( x ).

Худший случай [ править ]

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

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

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

Сводка времени работы [ править ]

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

Операцияfind-mindelete-minвставлятьклавиша уменьшенияобъединить
Двоичный [8]Θ (1)Θ (журнал  n )O (журнал  n )O (журнал  n )Θ ( п )
ЛевыйΘ (1)Θ (журнал n )Θ (журнал n )O (журнал n )Θ (журнал n )
Биномиальный [8] [9]Θ (1)Θ (журнал n )Θ (1) [а]Θ (журнал n )O (log  n ) [b]
Фибоначчи [8] [2]Θ (1)O (log  n ) [a]Θ (1)Θ (1) [а]Θ (1)
Сопряжение [10]Θ (1)O (log n ) [a]Θ (1)о (журнал  п ) [а] [с]Θ (1)
Бродал [13] [d]Θ (1)O (журнал  n )Θ (1)Θ (1)Θ (1)
Ранговые пары [15]Θ (1)O (log n ) [a]Θ (1)Θ (1) [а]Θ (1)
Строгий Фибоначчи [16]Θ (1)O (журнал n )Θ (1)Θ (1)Θ (1)
2–3 кучи [17]O (журнал n )O (log n ) [a]O (log n ) [a]Θ (1)?
  1. ^ a b c d e f g h i Амортизированное время.
  2. ^ n - размер большей кучи.
  3. ^ Нижняя оценка [11] верхняя оценка [12]
  4. ^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением ключа уменьшения, который не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). [14]

Практические соображения [ править ]

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

Ссылки [ править ]

  1. ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «Глава 20: Кучи Фибоначчи». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 476–497. ISBN 0-262-03293-7.Издание третье с. 518.
  2. ^ a b c Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (июль 1987 г.). «Куча Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . DOI : 10.1145 / 28869.28874 .  
  3. ^ Фредман, Майкл Л .; Седжвик, Роберт ; Слейтор, Дэниел Д .; Тарджан, Роберт Э. (1986). «Кучка сопряжения: новая форма саморегулирующейся кучи» (PDF) . Алгоритмика . 1 (1–4): 111–129. DOI : 10.1007 / BF01840439 . S2CID 23664143 .  
  4. ^ Джерт Стлтинг Бродал (1996), "наихудший Efficient Очереди Priority" , Proc. Седьмые ACM-SIAM симпозиум по дискретным алгоритмам , Общество промышленной и прикладной математика : 52-58, CiteSeerX 10.1.1.43.8133 , DOI : 10.1145 / 313852.313883 (неактивного 2021-01-10) ISBN  0-89871-366-8CS1 maint: DOI неактивен с января 2021 г. ( ссылка )
  5. ^ Бродал, GSL; Lagogiannis, G .; Тарьян, Р. Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. п. 1177. DOI : 10,1145 / 2213977,2214082 . ISBN  978-1-4503-1245-5.
  6. ^ Мрена, Михал; Седлачек, Питер; Квасай, Мирослав (июнь 2019). «Практическая применимость расширенных реализаций очередей с приоритетом в поиске кратчайших путей». Международная конференция по информационным и цифровым технологиям (IDT) 2019 . Жилина, Словакия: IEEE: 335–344. DOI : 10.1109 / DT.2019.8813457 . ISBN 9781728114019. S2CID  201812705 .
  7. ^ a b Ларкин, Дэниел; Сен, Сиддхартха; Тарджан, Роберт (2014). «Основное эмпирическое исследование приоритетных очередей». Труды шестнадцатого семинара по разработке алгоритмов и экспериментов : 61–72. arXiv : 1403.0252 . Bibcode : 2014arXiv1403.0252L . DOI : 10.1137 / 1.9781611973198.7 . ISBN 978-1-61197-319-8. S2CID  15216766 .
  8. ^ a b c d Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
  9. ^ "Биномиальная куча | Блестящая математика и наука вики" . brilliant.org . Проверено 30 сентября 2019 .
  10. ^ Яконо, Джон (2000), "Улучшенные верхние границы для парных куч", Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , конспект лекций по информатике, 1851 , Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007 / 3-540-44985-X_5 , ISBN   3-540-67690-2
  11. ^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. DOI : 10.1145 / 320211.320214 .
  12. ^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. С. 174–183. CiteSeerX 10.1.1.549.471 . DOI : 10.1109 / SFCS.2005.75 . ISBN   0-7695-2468-0.
  13. ^ Бродал, Герт С. (1996), "Эффективные приоритетные очереди наихудшего случая" (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
  14. ^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Строительство кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.
  15. ^ Haeupler, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). "Куча ранговых пар" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. DOI : 10.1137 / 100785351 .
  16. ^ Бродал, Герт Стёльтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. С. 1177–1184. CiteSeerX 10.1.1.233.1740 . DOI : 10.1145 / 2213977.2214082 . ISBN   978-1-4503-1245-5.
  17. ^ Такаок, Тадао (1999), Теория 2-3 куч (PDF) , стр. 12
  18. ^ http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf , стр. 79
  19. ^ http://web.stanford.edu/class/cs166/lectures/07/Small07.pdf , стр. 72

Внешние ссылки [ править ]

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