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