You should also compare the implementations of those algorithms. You also have to know what size your data might be. You should probably stay away from Fibonacci heaps , which have good asymptotic performance but have slow implementations unless N is huge. The expected case behavior of heaps here is equivalent to the worst case behavior. We may be able to do better if we find a data structure where expected case is better, even if the worst case is no better.
Splay trees are a self adjusting tree structure.
Any access to a node in the tree tends to bring that node up to the top. There's another good data structure that may be better than heaps. Often, you can restrict the range of values that would be in the priority queue. Given a restricted range, there are often better algorithms. The constant C is the maximum change in cost from one point to an adjacent point.