Module PsqSource

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