Существует ли стандартная реализация Java кучи Fibonacci?

Я смотрел на различные типы структур данных кучи.

Кажется, что куча Фибоначчи имеет лучшую худшую сложность для (1) вставки, (2) удаления и (2) нахождения минимального элемента.

Я обнаружил, что в Java есть класс PriorityQueue, который представляет собой сбалансированную двоичную кучу. Но почему они не использовали кучу Фибоначчи?

Кроме того, существует ли реализация кучи Фибоначчи в java.util?

Спасибо!

Ответы

Ответ 1

Нет, стандартный API Java-сборников не содержит реализации кучи Фибоначчи. Я не уверен, почему это так, но я считаю, что это связано с тем, что в то время как кучи Фибоначчи асимптотически велики в амортизированном смысле, на практике они имеют огромные постоянные факторы. Рамка коллекций также не имеет биномиальной кучи, которая была бы еще одной полезной кучей.

Как совершенно бесстыдная самозапуск, у меня есть реализация кучи Fibonacci в Java на моем личном веб-сайте. Я не уверен, насколько это будет полезно, но если вам интересно посмотреть, как это работает, я думаю, что это может быть хорошей отправной точкой.

Надеюсь, это поможет!

Ответ 2

Но почему они не использовали кучу Фибоначчи?

Возможно, потому что эти кучи имеют намного больше накладных расходов на запись, чем двоичные ключи.

Кроме того, есть ли реализация кучи Фибоначчи в Java.util?

Нет, но

  1. Есть создатель графиков от Натана Фидлера - GPL и с хорошим тестовым освещением, но взгляните на этот хороший пост в блоге об этом и о проблемах, которые могут возникнуть у Фибоначчи. В этом посте упоминается множество других реализаций Java.
  2. Существует некоторый код с юнит - тестов здесь
  3. Проект JGraphT (также Натан Фидлер), а также с (некоторыми незначительными) тестами, но LGPL.
  4. И последнее, но не менее важное: Neo4j - GPL - тестов нет.

Ответ 3

Но почему они не использовали кучу Фибоначчи?

Я думаю, что основная причина заключается в том, что куча Фибоначчи может помочь только в том случае, когда у вас есть намного больше операций уменьшения активности, связанных с одной операцией extractMin. Например, когда вы используете его с алгоритмом Дейкстры.

Кроме того, существует ли реализация кучи Fibonacci в Java.util?

В Java.util нет реализации, но я провел эксперимент по этой теме, используя существующие версии с открытым исходным кодом кучи Фибоначчи. Вы можете найти его в моем блоге или в проект репозитория GitHub.