[icarus127]

You may be interested in this paper www.cs.ox.ac.uk/ralf.hinze/publications/ICFP01.pdf. It solves Dijkstra's algorithm as an example for the implementation of a priority search queue data structure, which is very similar to a priority search tree. These structures act as a heap on one index and a search tree on a second index. So you get both efficient update and find-min.

[fbrusch]

I think your link is the perfect answer to the problem highlighted in the post (which is, incidentally, a problem I was facing myself, so thank you!). There's also an Haskell implementation of priority search queues: http://hackage.haskell.org/package/PSQueue-1.1/docs/Data-PSQ...