module type S =sig
..end
type 'a
t
include Container.S1
val create : ?min_size:int -> cmp:('a -> 'a -> int) -> unit -> 'a t
create ?min_size ~cmp
returns a new min-heap that can store min_size
elements
without reallocations, using ordering function cmp
.
The top of the heap is the smallest element as determined by the provided comparison
function. In particular, if cmp x y < 0
then x
will be "on top of" y
in the
heap.
Memory use is surprising in two ways:
1. The underlying pool never shrinks, so current memory use will at least be proportional to the largest number of elements that the heap has ever held.
2. Not all the memory is freed upon remove
, but rather after some number of
subsequent pop
operations. Alternating add
and remove
operations can therefore
use unbounded memory.
val of_array : 'a array -> cmp:('a -> 'a -> int) -> 'a t
min_size
(see create
) will be set to the size of the input array or list.val of_list : 'a list -> cmp:('a -> 'a -> int) -> 'a t
val top : 'a t -> 'a option
val top_exn : 'a t -> 'a
val add : 'a t -> 'a -> unit
val remove_top : 'a t -> unit
remove_top t
does nothing if t
is emptyval pop : 'a t -> 'a option
val pop_exn : 'a t -> 'a
val pop_if : 'a t -> ('a -> bool) -> 'a option
pop_if t cond
returns Some top_element
of t
if it satisfies condition
cond
, removing it, or None
in any other case.val copy : 'a t -> 'a t
copy t
returns a shallow copyval sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
create ?min_size ~cmp
returns a new min-heap that can store min_size
elements
without reallocations, using ordering function cmp
.
The top of the heap is the smallest element as determined by the provided comparison
function. In particular, if cmp x y < 0
then x
will be "on top of" y
in the
heap.
Memory use is surprising in two ways:
1. The underlying pool never shrinks, so current memory use will at least be proportional to the largest number of elements that the heap has ever held.
2. Not all the memory is freed upon remove
, but rather after some number of
subsequent pop
operations. Alternating add
and remove
operations can therefore
use unbounded memory.
min_size
(see create
) will be set to the size of the input array or list.
returns the top (i.e., smallest) element of the heap
remove_top t
does nothing if t
is empty
This removes and returns the top (i.e. least) element
pop_if t cond
returns Some top_element
of t
if it satisfies condition
cond
, removing it, or None
in any other case.
copy t
returns a shallow copy