module Heap:
A functor that produces a module of type Cf_heap to represent heaps with
the element type described by E.
type
The heap type
module Element: sig .. end
A module defining the type of the element.
val nil : t
The empty heap.
val empty : t -> bool
Use empty h to test whether the heap h is empty.
val size : t -> int
Use size h to count the number of elements in the heap h. Runs
in O(n) time and O(log N) space.
val head : t -> Element.t
Use head h to obtain the element on the top of the heap h. Raises
Not_found if the heap is empty.
val tail : t -> t
Use tail h to obtain the heap produced by discarding the element on
the top of heap h. If h is the empty heap, then the empty heap is
returned.
val pop : t -> (Element.t * t) option
Use pop h to obtain the head and the tail of a heap h in one
operation. Returns None if the h is empty.
val put : Element.t -> t -> t
Use put e h to obtain a new heap that is the result of inserting
the element e into the heap h.
val merge : t -> t -> t
Use merge h1 h2 to obtain a new heap that is the result of merging
all the elements of h1 and h2 into a single heap.
val iterate : (Element.t -> unit) -> t -> unit
Use iterate f h to apply f to every element in the heap h in an
arbitrary order (not top to bottom). Runs in O(n) time and O(1) space.
val predicate : (Element.t -> bool) -> t -> bool
Use predicate f h to test whether all the elements in heap h
satisfy the predicate function f. Runs in O(n) time (with a short
cut when an element is found to fail the predicate) and O(1) space.
Visits the elements in the heap in arbitrary order (not top to bottom).
val fold : ('b -> Element.t -> 'b) -> 'b -> t -> 'b
Use fold f s h to produce the result of folding a value s into
the elements of heap h with the folding function f in an arbitrary
order (not top to bottom). Runs in O(n) time and O(1) space.
val filter : (Element.t -> bool) -> t -> t
Use filter f h to apply f to each element in the heap h in an
arbitrary order (not to top bottom), and produce a new heap that
contains only those elements for which f pair returned true.
val partition : (Element.t -> bool) -> t -> t * t
Use partition f h to obtain a pair of new heaps that are the result
of applying the partitioning function f to each element in the heap
h in an arbitrary order (not top to bottom). The first heap returned
will contain all the elements for which f pair returned true, and the
second heap will return all the remaining elements.
val of_seq : Element.t Cf_seq.t -> t
Use of_seq z to construct a heap from a sequence of elements.
Evaluates the whole sequence. Runs in O(n) time and O(1) space.
val of_list : Element.t list -> t
Use of_list s to construct a heap from a list of elements. Runs in
O(n) time and O(1) space.
val to_seq : t -> Element.t Cf_seq.t
Use to_seq h to produce a sequence of elements in top to bottom order
from the heap h.
val to_seq2 : t -> (Element.t * t) Cf_seq.t
Use to_seq2 h to produce a sequence of elements from the heap h
where the first element of each pair is a key-value pair obtained from
the head of the heap, and the second element of the pair is the
corresponding tail of the heap.