Comment by noctune

You can use a radix heap rather than a binary heap. I have an implementation here, with benchmarks using pathfinding: https://github.com/mpdn/radix-heap

It has the nice property that the amortized cost of pushing/popping an element is independent of the number of other elements in the heap.