@hackage psqueues0.1.0.0

A priority search queue manages a set of triples of the form (key, priority, value) and allows for efficient lookup by key, and efficient lookup and removal of the element with minimal priority. This package contains three, performant implementations of priority search queues, which differ in the requirements on the type of keys.

• IntPSQs are the most efficient structure, but require the keys to be of type Int.

• OrdPSQs just require the key to implement the Ord typeclass, but are the slowest structures of the three.

• HashPSQs require the key to implement both the Ord and Hashable typeclasses. They use an IntMap over the hash of the keys combined with a OrdPSQ to manage collisions. Except for keys with a very fast comparison and small smaps HashPSQs are faster than OrdPSQs.

Typical use cases for priority search queues are LRU caches, where the priority is the time of the last access, and timeout management, where the priority is the time at which the timeout should trigger.