Module `Psq`

Functional Priority Search Queues

Psq provides a functional structure that behaves as both a finite map and a priority queue.

The structure contains a collection of bindings k -> p, and allows efficient addition, lookup and removal of bindings by key.
It additionally supports access to, and removal of the binding k -> p with the least p.

The implementation is backed by a weight-balanced semi-heap. Access by key is O(log n). Access to the minimal p is O(1), and its removal is O(log n).

References

Ralf Hinze. A Simple Implementation Technique for Priority Search Queues. 2001.

v0.2.0-7-gb2eb861 — homepage

Psq

module type S = sig ... end

Signature of priority search queues.

module type Ordered = sig ... end

Signature of ordered types.

module Make (K : Ordered) (P : Ordered) : S with type k = K.t and type p = P.t

Make(K)(P) is the priority search queue with bindings K.t -> P.t.