Module Prime_priqueue.Make

Parameters

• Elt : Stdlib.Set.OrderedType

Signature

type elt = Elt.t

type t

val empty : t

The empty queue.

val is_empty : t -> bool

is_empty q is true iff q has no elements.

val add : elt -> t -> t

add e q is q with an additional element e, keeping duplicates.

val remove : elt -> t -> t

remove e q is q with one e element removed, if any. The implementation adds a node marking e for deletion, if an element e would not be immediatly accessible if present, but care is taken that later additions of e is unaffected by the deletion marker.

val find_min : t -> elt

find_min q is the minimal element of q.

raises Not_found

if q is empty.

val remove_min : t -> t

remove_min q is q with one less copy of its minimal element.

val pop_min : t -> (elt * t) option

pop_min q gives the minimum element of q and q without the same element if q is non-empty.

val gc : t -> t

gc q is an optimised queue containing the same elements as q. It is built from the empty queue, adding each element of q.