module Heap:`sig`

..`end`

Min-heap implementation, adapted from CLR.

`exception Empty`

Raised when

`top`

or `pop`

is called on an empty heap.`type ``'el`

t

Type of heaps

`include Container.S1`

`type ``'el`

heap_el

Type of heap elements (they can be efficiently removed)

`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 heap`val 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`

Type of heap elements (they can be efficiently removed)

`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.