it seems that you need an implementation of the abstract data type “priority queue” with operations like:
- create
- change key (decrease and/or increase)
- insect
- delete (only item with min key or any item?)
- findmin
The “best” implementation depends on the number of times each operation is called.
Furthermore, if you know something about the range of the possible keys you might use that information to speedup your implementation.
Within the area of shortest path calculations where the arc costs are integers bounded by a constant C you might use the Bucket implementation of Dial.
In case of non-integer keys or when you encounter multiple empty buckets you can search for multilevel bucket implementations or buckets that contant a range of keys.
Again, since there are a lot of possible implementations I can’t provide an answer. But you might search for shortest path implementations a lot of the literature is about a priority queue.
Just one other idea derived from shortest path algorithms on large scale graphs (10M nodes) usually visit often only a few nodes (~10K). Then it might make sense to not create a priority queue that reserves memory for the keys of nodes. A better idea might be to implement an ISet, which easily can be done using a dictionary.