идея проекта для кучи Фибоначчи

Question

Я нахожусь в классе компьютерного программирования начального уровня, и я (вместе с 3 другими студентами) хочу реализовать кучу Фибоначчи для конечного проекта. Кто-нибудь может предложить несколько хороших применений кучи Фибоначчи? Что-то достаточно кричащее, чтобы быть хорошим презентационным материалом?

Answer 1

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

Имейте в виду: хотя кучи Фибоначчи теоретически оптимальны, они, как правило, превосходят двоичные кучи по двум вышеупомянутым проблемам. Чтобы куча Фибоначчи действительно сияла, вам понадобится один из следующих случаев: а) Дорогие сравнения: кучи Fib минимизируют количество сравнений, необходимых для организации данных. б) Большинство операций это updateKey / insert / delete. Поскольку Fibonacci Heaps «группирует» обновления до следующего extractMin, чем больше «пакет», тем эффективнее он становится.

Answer 2

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