Priority queue with a buffer for delayed insertion and other tweaks
There are several approaches that combine multiple buckets and heaps to improve shortest path algorithms. At good starting point would be Dial's algorithm or Cherkassky, Goldberg &amp; Silverstein.