Module Bounded_min_heap.Make

Make (ID) (E) creates a min heap for element of type E.t using the E.compare function. The heap is bounded and adding more elements than its capacity will fail. The module ID is used to check if an element already exists at insertion.

Parameters

module Id : Stdlib.Hashtbl.HashedType
module E : sig ... end

Signature

module Hash_map : Stdlib.Hashtbl.S with type key := Id.t
type t
val create : int -> t

create capacity creates a bounded sequence of at most capacity elements.

Raise Invalid_argument if size < 0 or size > Sys.max_array_length.

val insert : E.t -> t -> (unit, string) Stdlib.result

insert e h adds element e to bounded sequence h if h is not full.

Worst-case complexity: O(log n) where n is the capacity of the heap.

If there is an element e' with E.id e' = E.id e, it will be replaced iff E.compare e e' < 0 .

val pop : t -> E.t option

pop h removes the smallest element from the heap h, None if empty.

val peek_min : t -> E.t option

peek_min h returns, without removing, the smallest element from the heap h, None if empty.

val elements : t -> E.t list

elements h returns the contents of h as a sorted list in increasing order according to E.compare.

Worst-case complexity: O(n log n) where n is the size of the heap.

val length : t -> int

length h is the number of elements held by h.

val mem : E.t -> t -> bool

mem elt h returns true is the elt already exists in h, i.e. E.compare returns 0.

val find_opt : Id.t -> t -> E.t option

find id h returns the first elements of h, that as E.id e = id is true.

val remove : t -> Id.t -> unit

remove h id removes the element with id from the heap, or leaves h unchanged if id is not present in h.

val remove_predicate : (E.t -> bool) -> t -> Id.t list

remove_predicate f h removes the elements elt for which f elt = true from the heap and returns the list of ids removed.

val clear : t -> unit

clear h deletes all data from the heap.

module Internal_for_tests : sig ... end