Module type CCHeap.S

type elt
type t
val empty : t

Empty heap.

val is_empty : t ‑> bool

Is the heap empty?

exception Empty
val merge : t ‑> t ‑> t

Merge two heaps.

val insert : elt ‑> t ‑> t

Insert a value in the heap.

val add : t ‑> elt ‑> t

Synonym to insert.

val filter : (elt ‑> bool) ‑> t ‑> t

Filter values, only retaining the ones that satisfy the predicate. Linear time at least.

val find_min : t ‑> elt option

Find minimal element.

val find_min_exn : t ‑> elt

Like find_min but can fail.

val take : t ‑> (t * elt) option

Extract and return the minimum element, and the new heap (without this element), or None if the heap is empty.

val take_exn : t ‑> t * elt

Like take, but can fail.

val delete_one : (elt ‑> elt ‑> bool) ‑> elt ‑> t ‑> t

Delete one occurrence of a value if it exist in the heap. delete_one eq x h, use eq to find one x in h and delete it. If h do not contain x then it return h.

val delete_all : (elt ‑> elt ‑> bool) ‑> elt ‑> t ‑> t

Delete all occurrences of a value in the heap. delete_all eq x h, use eq to find all x in h and delete them. If h do not contain x then it return h. The difference with filter is that delete_all stops as soon as it enters a subtree whose root is bigger than the element.

val iter : (elt ‑> unit) ‑> t ‑> unit

Iterate on elements.

val fold : ('a ‑> elt ‑> 'a) ‑> 'a ‑> t ‑> 'a

Fold on all values.

val size : t ‑> int

Number of elements (linear complexity).

Conversions

The interface of of_gen, of_seq, of_klist has changed since 0.16 (the old signatures are now add_seq, add_gen, add_klist).

val to_list : t ‑> elt list

Return the elements of the heap, in no particular order.

val to_list_sorted : t ‑> elt list

Return the elements in increasing order.

val add_list : t ‑> elt list ‑> t

Add the elements of the list to the heap. An element occurring several times will be added that many times to the heap.

val of_list : elt list ‑> t

of_list l is add_list empty l. Complexity: O(n log n).

val add_seq : t ‑> elt sequence ‑> t
val of_seq : elt sequence ‑> t

Build a heap from a given sequence. Complexity: O(n log n).

val to_seq : t ‑> elt sequence

Return a sequence of the elements of the heap.

val to_seq_sorted : t ‑> elt sequence

Iterate on the elements, in increasing order.

val add_klist : t ‑> elt klist ‑> t
val of_klist : elt klist ‑> t

Build a heap from a given klist. Complexity: O(n log n).

val to_klist : t ‑> elt klist

Return a klist of the elements of the heap.

val add_gen : t ‑> elt gen ‑> t
val of_gen : elt gen ‑> t

Build a heap from a given gen. Complexity: O(n log n).

val to_gen : t ‑> elt gen

Return a gen of the elements of the heap.

val to_tree : t ‑> elt ktree

Return a ktree of the elements of the heap.

val pp : ?⁠sep:string ‑> elt printer ‑> t printer

Printer. Renamed from print since 2.0