Повысить операцию по уменьшению кучи Фибоначчи
Новая библиотека повышения «куча» включает в себя кучу Фибоначчи. Сложность каждой реализации можно увидеть здесь: http://www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structures.html.
Мой вопрос таков: почему операция уменьшения кучи Фибоначчи O (log (N)), а операция увеличения — O (1)?
Я хотел бы поэкспериментировать с использованием кучи Фибоначчи в алгоритме Дейкстры, который сильно зависит от операции быстрого уменьшения.
Решение
В соответствии с http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html
boost.heap реализует очереди с приоритетами в виде max-heaps, чтобы соответствовать функциям кучи STL. Это в отличие от типичного дизайна учебника, который использует минимальные кучи.
Учебник / википедия Куча Фибоначчи имеет элемент с наивысшим приоритетом с наименьшим значением, то есть минимальную кучу (например, «1» имеет более высокий приоритет, чем «2»). STL и Boost (для согласованности с STL) обращают определение таким образом, что наивысший приоритет имеет наибольшее значение, то есть максимальная куча (т. Е. «2» более высокий приоритет, чем «1»).
По сути это означает, что decrease а также increase имеют обратное значение между учебником и Boost.
Если вы хотите получить минимальную кучу (как определения из учебника), вы должны сначала определить соответствующий boost::heap::compare функтор для вашего fibonacci_heap (см. пример здесь: Определение функции сравнения для кучи Фибоначчи в бусте), затем позвоните increase всякий раз, когда вы уменьшаете значение, связанное с элементом кучи (и, таким образом, увеличиваете приоритет) и наоборот.
Другие решения
Других решений пока нет …