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