Esiste un'implementazione Java standard di un heap di Fibonacci?

Question

Stavo osservando il diverso tipo di strutture di dati dell'heap.

L'heap di Fibonacci sembra avere la migliore complessità del caso peggiore per (1) inserimento, (2) cancellazione e (2) ricerca dell'elemento minimo.

Ho trovato che in Java esiste una classe PriorityQueue che è un heap binario bilanciato. Ma perché non hanno usato un mucchio di Fibonacci?

Inoltre, esiste un'implementazione di un heap di Fibonacci in java.util?

Grazie!

Answer 1

No, l'API delle raccolte Java standard non contiene un'implementazione di un heap di Fibonacci. Non sono sicuro del perché questo sia, ma credo che sia perché gli heap di Fibonacci sono asintoticamente grandi in senso amortizzato, hanno enormi fattori costanti nella pratica. Anche il framework delle collezioni non ha un heap binomiale, che sarebbe un altro buon heap da includere.

Come plug-in totalmente svergognato, ho an implementation of a Fibonacci heap in Java on my personal website. Non sono sicuro di quanto sarà utile, ma se sei curioso di vedere come funziona, penso che potrebbe essere un buon punto di partenza.

Spero che questo aiuti!

Answer 2

Ma perché non hanno utilizzato un heap di Fibonacci?

Probabilmente perché questi heap hanno un sovraccarico molto maggiore per entrata rispetto alle chiavi binarie.

Inoltre, è presente un'implementazione dell'heap di Fibonacci in Java.util?

No, ma

3. C'è graphmaker da Nathan Fiedler - GPL e con buona test coverage, ma hanno uno sguardo in this nice blog post su di esso e circa problemi di Fibonacci impl può avere. In questo post vengono referenziate molte altre implementazioni Java.
4. Sussiste qualche codice con unità test here
5. Il JGraphT project (anche Nathan Fiedler) e con (alcuni minori) tests ma LGPL.
6. Ultimo ma non meno importante c'è Neo4j - GPL - nessun test.

Answer 3

Ma perché non hanno usato un mucchio di Fibonacci?

Penso che il motivo principale sia perché l'heap di Fibonacci può essere d'aiuto solo nel caso in cui si abbia molta più operazione di diminuzione della connessione collegata a un'operazione extractMin. Ad esempio, quando lo si utilizza con l'algoritmo di Dijkstra.

Inoltre, è presente un'implementazione dell'heap di Fibonacci in Java.util?

Non c'è implementazione in Java.util, ma ho fatto qualche esperimento su questo argomento usando versioni open-source esistenti dell'heap di Fibonacci. Lo puoi trovare on my blog o sul project's GitHub repository.