This is an implementation of functional priority queues in portable R6RS Scheme (plus one SRFI library).
These queues are based on a rooted, functional variety of binomial trees, first described by David J. King in Functional Binomial Queues (1994) and redesigned by G. S. Brodal & Chris Okasaki in Optimal purely functional priority queues (1996). Access to the least element in a queue takes constant time, and the other basic queue operations run in logarithmic time. In practice, these queue seem very fast, comparable to imperative implementations.
This library is in development. The interface could change at any time.
FTP. The tarball includes the library source and a test suite.
The SRFI 128 comparator library is required. SRFIs 1 and 64 are required to run the included tests.
The delete and decrease-key operations aren’t yet implemented. As Brodal & Okasaki note in their paper, these are difficult to implement efficiently on functional trees.
King actually implements decrease-key as a simple insertion (which falls back to identity on the queue when the key isn’t found). This is probably fine in many cases, but it can obviously blow up space-usage if you use a lot of decrease-key operations.
A priority queue (“pqueue”) represents a homogeneous fully-ordered sequence.
The type and ordering of a priority queue is defined by an embedded SRFI 128 comparator object (with mandatory type-test, equality, and ordering predicates).
(pqueue comparator element …) →
pqueue
Returns a priority queue with the given elements. Each element must satisfy comparator’s type-test predicate. Runs in O(m log n) time, where m is the number of elements.
(pqueue? obj) → boolean
Returns #t if obj is a priority queue and
#f otherwise.
(pqueue-empty? pqueue) → boolean
Returns #t if pqueue is empty and
#f otherwise.
(pqueue-min pqueue) → *
Returns the least element of pqueue, defined by pqueue’s ordering. If pqueue is empty, an assertion violation is signaled. Runs in O(1) time.
(pqueue-element-comparator pqueue) →
comparator
Returns pqueue’s embedded element comparator.
(pqueue-delete-min pqueue) → pqueue
Returns a priority queue with the same type predicate and ordering as pqueue, and with the same elements except for the least. An assertion violation is signaled if pqueue is empty. Runs in O(log n) time.
(pqueue-meld pqueue …) → pqueue
Returns a priority queue containing all of the elements of the
pqueues. While the pqueues may have different
comparators (in the sense of eqv?), they must define the
same element type and equality and ordering relations. Otherwise, an
assertion violation is signaled.
(pqueue->list pqueue) → list
Returns a list of the elements of pqueue in an unspecified order. Runs in O(n) time.
(pqueue-size pqueue) → exact-integer
Returns the number of elements in pqueue. Runs in O(log n) time.
© 2024--2026 by Wolfgang Corcoran-Mathe
Licensed under the MIT (Expat) license.
D. J. King (1994) Functional binomial queues. Glasgow Workshop on Functional Programming, p. 141–150. (PDF)
Gerth Stølting Brodal & Chris Okasaki (1996) Optimal purely functional priority queues. Journal of Functional Programming 6, p. 836–857. (PDF)