Существует ли стандартная реализация Java кучи Фибоначчи?
Я смотрел на различные виды структур данных кучи.
Куча Фибоначчи, кажется, имеет лучшую сложность в худшем случае для (1) вставки, (2) удаления и (2) нахождения минимального элемента.
Я обнаружил, что в Java есть класс PriorityQueue это сбалансированная двоичная куча. Но почему они не использовали кучу Фибоначчи?
Кроме того, есть ли реализация кучи Фибоначчи в java.util?
Спасибо!
3 ответа
Нет, стандартный API коллекций Java не содержит реализацию кучи Фибоначчи. Я не уверен, почему это так, но я полагаю, что это так, потому что, хотя кучи Фибоначчи асимптотически велики в амортизированном смысле, на практике они имеют огромные постоянные факторы. Платформа коллекций также не имеет биномиальной кучи, которая была бы еще одной хорошей кучей для включения.
В качестве бесстыдного самостоятельного подключения у меня есть реализация кучи Фибоначчи на Java на моем личном веб-сайте. Я не уверен, насколько это будет полезно, но если вам интересно посмотреть, как это работает, я думаю, что это может быть хорошей отправной точкой.
Надеюсь это поможет!
Но почему они не использовали кучу Фибоначчи?
Возможно, потому что эти кучи имеют намного больше накладных расходов на запись, чем двоичные ключи.
Кроме того, есть ли реализация кучи Фибоначчи в Java.util?
Нет, но
- Есть создатель графиков от Натана Фидлера - GPL и с хорошим тестовым освещением, но взгляните на этот хороший пост в блоге об этом и о проблемах, которые могут возникнуть у Фибоначчи. В этом посте упоминается множество других реализаций Java.
- Здесь есть код с юнит-тестами
- Проект JGraphT (также Натан Фидлер), а также с (некоторыми незначительными) тестами, но LGPL.
- И последнее, но не менее важное: Neo4j - GPL - тестов нет.
Но почему они не использовали кучу Фибоначчи?
Я думаю, что основная причина в том, что куча Фибоначчи может помочь только в том случае, если у вас есть намного больше операции lowerKey, связанной с одной операцией extractMin. Например, когда вы используете его с алгоритмом Дейкстры.
Кроме того, есть ли реализация кучи Фибоначчи в Java.util?
В Java.util реализации нет, но я провел некоторый эксперимент по этой теме, используя существующие версии кучи Фибоначчи с открытым исходным кодом. Вы можете найти его в моем блоге или в репозитории GitHub проекта.