(pqueues): Priority queues

This is an implementation of functional priority queues in portable Scheme (in an R6RS library wrapper).

These queues are based on a functional variety of binomial trees, first described by David J. King in Functional Binomial Queues (1994). The 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.

Contents

1. Source
2. Dependencies
3. Issues
4. Specification
   1. Constructors
   2. Predicates
   3. Accessors
   4. Updaters
   5. The whole pqueue
   6. Iteration
5. Copyright
6. References

Source

pqueues.sls (PGP signature).

A tarball including the library and a (SRFI 64) test suite can be found on FTP.

Dependencies

SRFIs 1, 9, and 128 are required.

The only R6RS dependencies at the moment are a couple of forms from (rnrs base (6)), notably assert and assertion-violation. Shim these and the library becomes fairly portable.

Issues

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.

Specification

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).

Constructors

(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.

Predicates

(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.

Accessors

(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(log n) time.

(pqueue-element-comparator pqueue) → comparator

Returns pqueue’s embedded element comparator.

Updaters

(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-pop pqueue) → [* pqueue]

Returns two values: the least element of pqueue and a new pqueue containing all of the other elements of pqueue. This is equivalent to:

(values (pqueue-min pqueue)
        (pqueue-delete-min pqueue))

but will usually be more efficient. 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. The comparator of the resulting pqueue is taken from one of the arguments (which is unspecified). While the pqueues may have different comparators (in the sense of eqv?), they must define the same element type and equality and ordering relations. (This is not checked.)

The whole pqueue

(pqueue-size pqueue) → exact-integer

Returns the number of elements in pqueue. Runs in O(log n) time.

Iteration

Priority-queue folds iterate by successively popping elements from the pqueue(s) until they are all empty. When more than one pqueue is folded, all pqueues must be of the same length. If they are not, an assertion violation is signaled.

(pqueue-fold-right proc base pqueue1 pqueue2 …) → *

Right folds proc over the elements of the pqueues in order. proc is invoked as (proc e1 e2 … seed), where e_i is an element drawn from pqueue_i.

Example

(pqueue-fold-right cons '() (pqueue integer-comparator 3 2 1))
  ⇒ (1 2 3)

(pqueue-fold-left proc base pqueue1 pqueue2 …) → *

Left folds proc over the elements of the pqueues in order. proc is invoked as (proc seed e1 e2 …), where e_i is an element drawn from pqueue_i.

Copyright

© 2024--2026 by Wolfgang Corcoran-Mathe

Licensed under the MIT (Expat) license.

References

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)

Home