Има ли стандартна Java реализация на купчина на Фибоначи?

Разглеждах различни видове структури от данни за купчина.

Купчината на Фибоначи изглежда има най-добрата сложност в най-лошия случай за (1) вмъкване, (2) изтриване и (2) намиране на минималния елемент.

Открих, че в Java има клас PriorityQueue, който е балансирана двоична купчина. Но защо не са използвали купчина на Фибоначи?

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

Благодаря!


java data-structures heap fibonacci-heap
person Phil    schedule 08.06.2011    source източник
comment
java колекциите предоставят само най-често срещаните структури от данни. Предполагам, че купчината на Фибоначи е по-специализирана или може би използва повече памет.   -  person Denis Tulskiy    schedule 08.06.2011
comment
@James, какво значение има това с купчината на Фибоначи? о.о   -  person ignis    schedule 08.06.2011
comment
algs4.cs.princeton.edu/code/ javadoc/edu/princeton/cs/algs4/   -  person maplemaple    schedule 22.08.2019

Отговори (3)


arrow_upward
49
arrow_downward

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

Като напълно безсрамен самовключващ се, имам имплементация на Fibonacci heap в Java на моя личен уебсайт. Не съм сигурен колко полезно ще бъде, но ако сте любопитни да видите как работи, мисля, че може да е добра отправна точка.

Надявам се това да помогне!

person templatetypedef    schedule 08.06.2011
comment
Благодаря много. Вашето внедряване изглежда добре направено и добре документирано с много обяснения. Ще разгледам това. - person Phil; 08.06.2011
comment
Леле, щях да напиша моя собствена за забавление, но вашата е толкова хубава! - person Andy; 18.12.2013
comment
Как се представя в действителност? Купчината на Фибоначи изглежда има доста голяма памет. - person Has QUIT--Anony-Mousse; 09.10.2015
comment
@Anony-Mousse Фибоначи купчините са известни като бавни на практика точно поради причината, която споменахте. - person templatetypedef; 09.10.2015

arrow_upward
5
arrow_downward

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

Вероятно защото тези купчини имат много повече разходи за запис, отколкото двоичните ключове.

Също така, има ли реализация на Fibonacci heap в Java.util?

Не но

  1. Има graphmaker от Nathan Fiedler - GPL и с добро тестово покритие, но погледнете тази хубава публикация в блог за това и за проблемите, които fibonacci impl може да има. В тази публикация се споменават много други реализации на Java.
  2. Има код с модулни тестове тук
  3. Проектът JGraphT (също Нейтън Фидлър), а също и с (някои второстепенни) тестове, но LGPL.
  4. Не на последно място има Neo4j - GPL - без тестове.
person Karussell    schedule 15.01.2012

arrow_upward
1
arrow_downward

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

Мисля, че основната причина е, защото купчината на Фибоначи може да помогне само в случай, когато имате много повече операция на smanjiване на ключ, свързана с една операция на екстрактМин. Например, когато го използвате с алгоритъма на Дейкстра.

Също така, има ли реализация на Fibonacci heap в Java.util?

Няма имплементация в Java.util, но направих някои експерименти по тази тема, използвайки съществуващи версии с отворен код на Fibonacci heap. Можете да го намерите в моя блог или на хранилището на GitHub на проекта.

person gabormakrai    schedule 12.02.2015
comment
Можете ли да уточните отговора си на първия въпрос - person arunmoezhi; 12.02.2015
comment
Разбира се че мога. Fibonacci Heap има превъзходство над Binary Heap при изпълнение на операциите за намаляване на ключ и вмъкване, също така има същата времева сложност за extractMin, но тази операция отнема много повече време за FH, отколкото за BH, защото консолидира гората от вътрешни дървета. Така че, ако имате много малко reduceKey, тогава той е по-бавен от нормалната двоична купчина. За някои специални графики това е случаят с алгоритъма на Дейкстра. - person gabormakrai; 13.02.2015