This paper presents a new implementation technique for priority search
queues. This abstract data type is an amazing blend of finite maps and
priority queues. Our implementation supports logarithmic access to a
binding with a given key and constant access to a binding with the
minimum value. Priority search queues can be used, for instance, to
give a simple, purely functional implementation of Dijkstra's single
source shortest-path algorithm.
A non-technical concern of the paper is to foster abstract data types
and views. Priority search queues have been largely ignored by the
functional programming community and we believe that they deserve to
be known better. Views prove their worth both in defining a convenient
interface to the abstract data type and in providing a readable
implementation.