Priority Queue - Fibonacci Heap Pass List

Question

I am interested in implementing a priority queue to provide an efficient implementation of Astar, which is also relatively simple (priority queue is simple, I mean).

It appears that since Skip List offers a simple O (1) extract-Min and an insert operation that is O (Log N), it can be competitive with a more complicated implementation of Fibonacci Heap, which has an O (log N) extract-Min and O (1). I believe that Skip-List would be better for a graph with sparse nodes, while a Fibonacci heap would be better for an environment with more tightly connected nodes.

This will probably make the Fibonacci bunch usually better, but do I correctly assume that Big-Oh wise they would be similar?

Answer 1

The difference in the Fibonacci heap is the operation with decreasing the key O (1), which allows the Dijkstra algorithm to work in time O (| V | log | V | + | E |). In practice, however, if I needed an efficient key reduction operation, I would use a pairing pair since the Fibonacci bunch has terrible constants. If your keys are small integers, it may even be better to use cells.

Answer 2

Fibonacci heaps are very very slow, with the exception of very very very large and dense graphs (of the order of hundreds of millions of edges). They are also difficult to implement correctly.

Skip lists, on the other hand, are very nice data structures and are relatively easy to implement.

However, I wonder why you are not considering using a simple binary heap. I believe that heap-based binary-cycle priority queues are even faster than list-based priority queues. Skip lists are mainly used to use concurrency.