A Simple Implementation Technique for Priority Search Queues

Ralf Hinze

To appear at International Conference on Functional Programming (ICFP01), Firenze, Italy, 3-5 September 2001


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.

Server START Conference Manager
Update Time 11 May 2001 at 15:31:50
Maintainer Xavier.Leroy@inria.fr.
Start Conference Manager
Conference Systems