ON THIS PAGE
package psq
Legend:
Library
Module
Module type
Parameter
Class
Class type

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

v0.2.0 — 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.