Fibonacci Heap provides function to fast retrieve the minimum cost, remove an element, update an element.
It seems that there is a generic PriorityQueue
class in Java. At least you could search for that
keyword. I have not used it since I prefer C#.
http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
http://en.literateprograms.org/Dijkstra's_algorithm_(Java)
Regards,
Joachim
The Java API does not provide a Fibonacci heap. The java.util.PriorityQueue is a binary heap. The Fibonacci heap is a rather specialized data structure. For standard priority queue operations the binary heap will actually be faster because the array implementation has low overhead. (The order is lower for some operations on the Fibonacci heap, but the overhead on it is higher and since standard usage is to insert and remove an equal number of elements, both are O(n log n) for doing so.) You use the Fibonacci heap is you need to merge heaps or decrease keys on elements as those operations are not efficient or easily done on binary heaps. If you really need those operations, you will have to either write your own or look for one in a 3rd party library.
Thanks very much for all, especially for Alim Gias. Yes, if only needs to get the minimum or insert an element, the PriorityQueue is a better choice. I think the implementation in the link looks good. It will be useful for me.
I did some experiment with using different versions of existing open-source Fibonacci heap implementations. I run the Dijkstra's algorithm with the help of the different Fibonacci heap's implementations. You can find the results on my blog https://gabormakrai.wordpress.com/2015/02/11/experimenting-with-dijkstras-algorithm/ or on the related GitHub page https://github.com/gabormakrai/dijkstra-performance.
https://gabormakrai.wordpress.com/2015/02/11/experimenting-with-dijkstras-algorithm/
https://github.com/gabormakrai/dijkstra-performance
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Programming Languages