Menu
I am interested in implementing a priority queue to enable an efficient Astar implementation that is also relatively simple (the priority queue is simple I mean).
It seems that because a Skip List offers a simple O(1) extract-Min operation and an insert operation that is O(Log N) it may be competitive with the more difficult to implement Fibonacci Heap which has O(log N) extract-Min and an O(1) insert. I suppose that the Skip-List would be better for a graph with sparse nodes whereas a Fibonacci heap would be better for an environment with more densely connected nodes.
This would probably make the Fibonacci Heap usually better, but am I correct in assuming that Big-Oh wise these would be similar?
530
In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap.
I've found that a skip list priority queue is often much more efficient than a binary heap. Also, pairing heap (which is not a traditional heap) is at fast or faster than binary heap, at least in my tests. Both of these do, on average, many fewer dereferences.
The heap provides multiple functions and operations than the priority queue. The priority queue provides queue-related functions. The heap implements abstract data types such as priority queue but priority queue does not implement heap. The priority queue is simpler than the heap data structure.
Fibonacci heaps also outperform binary heaps on insertion and merging (both amortized constant-time for Fibonacci heaps).
The raison d'etre of the Fibonacci heap is the O(1) decrease-key operation, enabling Dijkstra's algorithm to run in time O(|V| log |V| + |E|). In practice, however, if I needed an efficient decrease-key operation, I'd use a pairing heap, since the Fibonacci heap has awful constants. If your keys are small integers, it may be even better just to use bins.
87
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
