Module CCHeap.Make_from_compare

A convenient version of Make that take a TOTAL_ORD instead of a partially ordered module. It allow to directly pass modules that implement compare without implementing leq explicitly

Parameters

Signature

type elt = E.t
type t
val empty : t

empty returns the empty heap.

val is_empty : t -> bool

is_empty h returns true if the heap h is empty.

exception Empty
val merge : t -> t -> t

merge h1 h2 merges the two heaps h1 and h2.

val insert : elt -> t -> t

insert x h inserts an element x into the heap h.

val add : t -> elt -> t

add h x inserts an element x into the heap h.

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

filter p h filters values, only retaining the ones that satisfy the predicate p. Linear time at least.

val find_min : t -> elt option

find_min h find the minimal element of the heap h.

val find_min_exn : t -> elt

find_min_exn h is like find_min but can fail.

raises Empty

if the heap is empty.

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

take h extracts and returns the minimum element, and the new heap (without this element), or None if the heap h is empty.

val take_exn : t -> t * elt

take_exn h is like take, but can fail.

raises Empty

if the heap is empty.

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

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

since
2.0
val delete_all : (elt -> elt -> bool) -> elt -> t -> t

delete_all eq x h uses 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.

since
2.0
val iter : (elt -> unit) -> t -> unit

iter f h iterates over the heap h invoking f with the current element.

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

fold f acc h folds on all values of h.

val size : t -> int

size h is the number of elements in the heap h. Linear complexity.

Conversions

val to_list : t -> elt list

to_list h returns the elements of the heap h, in no particular order.

val to_list_sorted : t -> elt list

to_list_sorted h returns the elements of the heap h in increasing order.

since
1.1
val add_list : t -> elt list -> t

add_list h l adds the elements of the list l into the heap h. An element occurring several times will be added that many times to the heap.

since
0.16
val of_list : elt list -> t

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

val add_iter : t -> elt iter -> t

add_iter h iter is like add_list.

since
2.8
val add_seq : t -> elt Stdlib.Seq.t -> t

add_seq h seq is like add_list. Renamed from add_std_seq since 3.0.

since
3.0
val of_iter : elt iter -> t

of_iter iter builds a heap from a given iter. Complexity: O(n log n).

since
2.8
val of_seq : elt Stdlib.Seq.t -> t

of_seq seq builds a heap from a given Seq.t. Complexity: O(n log n). Renamed from of_seq since 3.0.

since
3.0
val to_iter : t -> elt iter

to_iter h returns a iter of the elements of the heap h.

since
2.8
val to_seq : t -> elt Stdlib.Seq.t

to_seq h returns a Seq.t of the elements of the heap h. Renamed from to_std_seq since 3.0.

since
3.0
val to_iter_sorted : t -> elt iter

to_iter_sorted h returns a iter by iterating on the elements of h, in increasing order.

since
2.8
val to_seq_sorted : t -> elt Stdlib.Seq.t

to_seq_sorted h returns a Seq.t by iterating on the elements of h, in increasing order. Renamed from to_std_seq_sorted since 3.0.

since
3.0
val add_gen : t -> elt gen -> t

add_gen h gen adds the gen gen to the heap h.

since
0.16
val of_gen : elt gen -> t

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

val to_gen : t -> elt gen

to_gen h returns a gen of the elements of the heap h.

val to_tree : t -> elt ktree

to_tree h returns a ktree of the elements of the heap h.

val to_string : ?⁠sep:string -> (elt -> string) -> t -> string

to_string ?sep f h prints the heap h in a string using sep as a given separator (default ",") between each element (converted to a string using f).

since
2.7
val pp : ?⁠pp_start:unit printer -> ?⁠pp_stop:unit printer -> ?⁠pp_sep:unit printer -> elt printer -> t printer

pp ?pp_start ?pp_stop ?pp_sep ppf h prints h on ppf. Each element is formatted with ppf, pp_start is called at the beginning, pp_stop is called at the end, pp_sep is called between each elements. By defaults pp_start and pp_stop does nothing and pp_sep defaults to (fun out -> Format.fprintf out ",@ "). Renamed from print since 2.0

since
0.16