Библиотеки Boost C ++ включают реализацию кучи Фибоначчи в boost/pending/fibonacci_heap.hpp. Этот файл, очевидно, был в pending/ в течение многих лет, и, по моим прогнозам, никогда не будет принят. Кроме того, в этой реализации были ошибки, которые исправил мой знакомый и крутой парень Аарон Виндзор. К сожалению, в большинстве версий этого файла, которые я смог найти в Интернете (и в версии Ubuntu libboost-dev), все еще были ошибки; Мне пришлось вытащить чистую версию из хранилища Subversion.
Начиная с версии 1.49 Boost C ++ библиотеки добавлено много новых структур кучи, включая кучу Фибоначчи.
Мне удалось скомпилировать dijkstra_heap_performance.cpp для модифицированной версии dijkstra_shortest_paths.hpp , чтобы сравнить кучи Фибоначчи и двоичные кучи. (В строке typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue измените relaxed на fibonacci.) Сначала я забыл скомпилировать с оптимизацией, и в этом случае кучи Фибоначчи и двоичные кучи работают примерно одинаково, причем кучи Фибоначчи обычно опережают на незначительную величину. После того, как я скомпилировал с очень сильными оптимизациями, двоичные кучи получили огромный импульс. В моих тестах кучи Фибоначчи превосходили только двоичные кучи, когда граф был невероятно большим и плотным, например ::1010*
Generating graph...10000 vertices, 20000000 edges.
Running Dijkstra's with binary heap...1.46 seconds.
Running Dijkstra's with Fibonacci heap...1.31 seconds.
Speedup = 1.1145.
Насколько я понимаю, это касается фундаментальных различий между кучами Фибоначчи и двоичными кучами. Единственное реальное теоретическое различие между этими двумя структурами данных заключается в том, что кучи Фибоначчи поддерживают ключ уменьшения (в амортизированном виде) постоянного времени. С другой стороны, двоичные кучи получают большую производительность от их реализации в виде массива; использование явной структуры указателя означает, что кучи Фибоначчи сильно страдают от производительности.
Таким образом, чтобы использовать на практике кучи Фибоначчи на практике , вы должны использовать их в приложении, в котором невероятно часто встречаются сокращения_ключей. В терминах Дейкстры это означает, что основной граф является плотным. Некоторые приложения могут быть внутренне уменьшены_ключом; Я хотел попробовать алгоритм минимального разреза Нагомочи-Ибараки , потому что, очевидно, он генерирует много ключей lower_keys, но было слишком много усилий, чтобы заставить работать сравнение по времени.
Предупреждение : Возможно, я сделал что-то не так. Вы можете попытаться воспроизвести эти результаты самостоятельно.
Теоретическое примечание : Улучшенная производительность кучи Фибоначчи при использовании кнопки less_key важна для теоретических приложений, таких как время выполнения Дейкстры. Кучи Фибоначчи также превосходят двоичные кучи при вставке и объединении (обе амортизируются постоянным временем для кучи Фибоначчи). Вставка, по сути, не имеет значения, потому что она не влияет на время выполнения Dijkstra, и довольно легко изменить двоичные кучи, чтобы также иметь вставку в амортизированном постоянном времени. Объединение в постоянное время является фантастическим, но не имеет отношения к этому приложению.
Личная заметка : Мой друг и я однажды написали статью, объясняющую новую очередь приоритетов, в которой была предпринята попытка воспроизвести (теоретическое) время работы кучи Фибоначчи без их сложности. Документ так и не был опубликован, но мой соавтор реализовал двоичные кучи, кучи Фибоначчи и нашу собственную очередь приоритетов для сравнения структур данных. Графики экспериментальных результатов показывают, что кучи Фибоначчи немного превосходят двоичные кучи с точки зрения общего сравнения, что позволяет предположить, что кучи Фибоначчи будут работать лучше в ситуации, когда стоимость сравнения превышает накладные расходы. К сожалению, у меня нет доступного кода, и, по-видимому, в вашей ситуации сравнение дешево, поэтому эти комментарии актуальны, но не имеют прямого отношения.
Кстати, я настоятельно рекомендую попытаться сопоставить время выполнения кучи Фибоначчи с вашей собственной структурой данных. Я обнаружил, что я просто заново изобрел кучу Фибоначчи. Раньше я думал, что все сложности кучи Фибоначчи были случайными идеями, но потом я понял, что все они были естественными и довольно вынужденными.