module Heap: Heap
exception Empty
top
or pop
is called on an empty heap.type 'el
t
include Container.S1
type 'el
heap_el
val heap_el_is_valid : 'el heap_el -> bool
heap_el_is_valid heap_el
true
iff heap element is member
of a heap.val heap_el_get_el : 'el heap_el -> 'el
heap_el_get_el heap_el
val heap_el_get_heap_exn : 'el heap_el -> 'el t
heap_el_get_heap_exn heap_el
Failure
if the element is not contained by some heapval get_cmp : 'el t -> 'el -> 'el -> int
get_cmp heap
heap
.val create : ?min_size:int -> ('el -> 'el -> int) -> 'el t
create ?min_size cmp
min_size
elements without reallocations, using ordering function cmp
.
If cmp x y < 0
(i.e. x < y), then x
will be on "top" of y
in the heap.
That is, Heap.pop will remove x
before y
.
val of_array : ?min_size:int -> ('el -> 'el -> int) -> 'el array -> 'el t
of_array ?min_size cmp ar
min_size
elements without reallocations, using ordering function
cmp
, and initialize it with the elements of ar
.val copy : 'el t -> 'el t
copy heap
heap
.val mem : 'el t -> 'el -> bool
mem heap el
true
iff el
is member of heap
.
Requires linear time in worst case.val heap_el_mem : 'el t -> 'el heap_el -> bool
heap_el_mem heap heap_el
true
iff heap_el
is member of
heap
. Requires constant time only.val find_heap_el_exn : 'el t -> 'el -> 'el heap_el
find_heap_el_exn heap el
Not_found
if el
could not be found.el
in heap
.val top : 'el t -> 'el option
top heap
Some top_element
of heap
without
changing it, or None
if heap
is empty.val top_exn : 'el t -> 'el
top_exn heap
Empty
if heap
is empty.heap
without changing it.val top_heap_el : 'el t -> 'el heap_el option
top_heap_el heap
Some top_heap_el
of heap
without
changing it, or None
if heap
is empty.val top_heap_el_exn : 'el t -> 'el heap_el
top_heap_el_exn heap
Empty
if heap
is empty.heap
without changing it.val fold_el : 'a t -> init:'b -> f:('b -> 'a heap_el -> 'b) -> 'b
fold_el heap ~f
fold over heap
with function f
. The elements
are passed in an unspecified order.val iter_el : 'a t -> f:('a heap_el -> unit) -> unit
iter_el heap ~f
iterate over heap
with function f
. The elements
are passed in an unspecified order.val pop : 'el t -> 'el option
pop heap
Some top_element
of heap
, removing it,
or None
if heap
is empty.val pop_exn : 'el t -> 'el
pop_exn heap
Empty
if heap
is empty.heap
, removing it.val pop_heap_el : 'el t -> 'el heap_el option
pop_heap_el heap
Some top_heap_element
, removing
it, or None
if heap
is empty.val pop_heap_el_exn : 'el t -> 'el heap_el
pop_heap_el_exn heap
Empty
if heap
is empty.heap
,
removing it.val cond_pop : 'el t -> ('el -> bool) -> 'el option
cond_pop heap cond
Some top_element
of heap
if it
fills condition cond
, removing it, or None
in any other case.val cond_pop_heap_el : 'el t -> ('el -> bool) -> 'el heap_el option
cond_pop_heap_el heap cond
Some top_heap_element
of
heap
if the associated element fills condition cond
, removing it,
or None
in any other case.val push : 'el t -> 'el -> 'el heap_el
push heap el
pushes element el
on heap
.val push_heap_el : 'el t -> 'el heap_el -> unit
push_heap_el heap heap_el
pushes heap_el
on heap
.Failure
if heap_el
is already member of some heap.val remove : 'el heap_el -> unit
remove heap_el
removes heap_el
from its associated heap.Failure
if heap_el
is not member of any heap.val update : 'el heap_el -> 'el -> unit
update heap_el el
updates heap_el
with element el
in its
associated heap.Failure
if heap_el
is not member of any heap.val check_heap_property : 'el t -> bool
check_heap_property h
asserts that h
has the heap property: that all
nodes are less than their children by h
's comparison function.val sexp_of_t : ('el -> Sexplib.Sexp.t) -> 'el t -> Sexplib.Sexp.t
val sexp_of_heap_el : ('el -> Sexplib.Sexp.t) -> 'el heap_el -> Sexplib.Sexp.t
heap_el_is_valid heap_el
heap_el_get_el heap_el
heap_el_get_heap_exn heap_el
get_cmp heap
create ?min_size cmp
of_array ?min_size cmp ar
copy heap
mem heap el
heap_el_mem heap heap_el
find_heap_el_exn heap el
top heap
top_exn heap
top_heap_el heap
top_heap_el_exn heap
fold_el heap ~f
fold over heap
with function f
. The elements
are passed in an unspecified order.iter_el heap ~f
iterate over heap
with function f
. The elements
are passed in an unspecified order.pop heap
pop_exn heap
pop_heap_el heap
pop_heap_el_exn heap
cond_pop heap cond
cond_pop_heap_el heap cond
push heap el
pushes element el
on heap
.push_heap_el heap heap_el
pushes heap_el
on heap
.remove heap_el
removes heap_el
from its associated heap.update heap_el el
updates heap_el
with element el
in its
associated heap.check_heap_property h
asserts that h
has the heap property: that all
nodes are less than their children by h
's comparison function.