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.