Идея проекта для кучи Фибоначчи
Я нахожусь в классе компьютерного программирования начального уровня, и я (вместе с 3 другими студентами) хочу реализовать кучу Фибоначчи для конечного проекта. Кто-нибудь может предложить несколько хороших применений кучи Фибоначчи? Что-нибудь достаточно кричащее, чтобы быть хорошим презентационным материалом?
2 ответа
Кучи Фибоначчи используются в некоторых графовых алгоритмах для улучшения их времени выполнения. Эти графические алгоритмы могут быть довольно "кричащими", поэтому вы можете продемонстрировать их. Например, я считаю, что алгоритм Дейкстры иногда использует кучи Фибоначчи для достижения лучшей асимптотической среды выполнения.
Есть много алгоритмов, которые (теоретически) выигрывают от эффективности кучи Фибоначчи, самый простой из которых - алгоритм Дейкстры для задач с кратчайшим путем и алгоритм Прима для минимальных остовных деревьев.
Имейте в виду: хотя кучи Фибоначчи теоретически оптимальны, они, как правило, превосходят двоичные кучи по двум вышеупомянутым проблемам. Чтобы куча Фибоначчи действительно сияла, вам понадобится один из следующих случаев: a) Дорогие сравнения: кучи Фибоначчи минимизируют количество сравнений, необходимых для организации данных. б) Большинство операций - updateKey / insert / delete. Поскольку Fibonacci Heaps "группирует" обновления до следующего extractMin, чем больше "пакет", тем эффективнее он становится.