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

Question

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

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

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

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

Спасибо!

Answer 1

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

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

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

Answer 2

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

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

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

Нет, но

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

Answer 3

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

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

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

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