module Fheap:sig
..end
type 'a
t
t_of_sexp
is not supported, because of the difficulty involved in recreating the
comparison function.include Container.S1
min_elt
, max_elt
, and to_list
are in Container.S1
, they are
documented separately to make sure there is no confusion.val min_elt : 'a t -> cmp:('a -> 'a -> int) -> 'a option
min_elt
and max_elt
are independent of that used to
order the heap. Since the provided cmp
may be different from the one used to
create the heap, it is necessary for these functions to traverse the entire heap. If
you want to access the smallest element of the heap according to the heap's comparison
function, you should use top
.val max_elt : 'a t -> cmp:('a -> 'a -> int) -> 'a option
val to_list : 'a t -> 'a list
to_list t
are not in any particular order. You need to sort the
list afterwards if you want to get a sorted list.val create : cmp:('a -> 'a -> int) -> 'a t
create ~cmp
returns a new min-heap that uses ordering function cmp
.
The top of the heap is the smallest element as determined by the provided comparison
function.
val of_array : 'a array -> cmp:('a -> 'a -> int) -> 'a t
val of_list : 'a list -> cmp:('a -> 'a -> int) -> 'a t
val add : 'a t -> 'a -> 'a t
add t v
returns the new heap after addition. Complexity O(1).val top : 'a t -> 'a option
val top_exn : 'a t -> 'a
val remove_top : 'a t -> 'a t option
remove_top t
returns the new heap after a remove. It does nothing if t
is empty.
The amortized time per remove_top t
(or pop t
, pop_exn t
, pop_if t
) is O(lg
n). The complexity of the worst case is O(n).
val pop : 'a t -> ('a * 'a t) option
val pop_exn : 'a t -> 'a * 'a t
val pop_if : 'a t -> ('a -> bool) -> ('a * 'a t) option
pop_if t cond
returns Some (top_element, rest_of_heap)
if t
is not empty and its
top element satisfies condition cond
, or None
in any other case.val to_sequence : 'a t -> 'a Sequence.t
to_sequence t
is a sequence of the elements of t
in ascending order.val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
min_elt
, max_elt
, and to_list
are in Container.S1
, they are
documented separately to make sure there is no confusion.min_elt
and max_elt
are independent of that used to
order the heap. Since the provided cmp
may be different from the one used to
create the heap, it is necessary for these functions to traverse the entire heap. If
you want to access the smallest element of the heap according to the heap's comparison
function, you should use top
.to_list t
are not in any particular order. You need to sort the
list afterwards if you want to get a sorted list.create ~cmp
returns a new min-heap that uses ordering function cmp
.
The top of the heap is the smallest element as determined by the provided comparison
function.
add t v
returns the new heap after addition. Complexity O(1).
This returns the top (i.e. smallest) element of the heap. Complexity O(1).
remove_top t
returns the new heap after a remove. It does nothing if t
is empty.
The amortized time per remove_top t
(or pop t
, pop_exn t
, pop_if t
) is O(lg
n). The complexity of the worst case is O(n).
This removes and returns the top (i.e. least) element and the modified heap.
pop_if t cond
returns Some (top_element, rest_of_heap)
if t
is not empty and its
top element satisfies condition cond
, or None
in any other case.
to_sequence t
is a sequence of the elements of t
in ascending order.