Module `Psq`Source

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

Sourcemodule type S = sig ... end

Signature of priority search queues.

Sourcemodule type Ordered = sig ... end

Signature of ordered types.

Source

module Make
  (K : Psq.Ordered)
  (P : Psq.Ordered) : 
  Psq.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.

Module PsqSource

Psq

Module `Psq`Source