I tried a Fibonacci heap for my implementation of Dijkstra's algorithm, but it ended up being slower! Apparently this is a common thing and Fibonacci heaps are very rare in practice: https://stackoverflow.com/q/30782636/509706