Up
# Module Heap

### Signature

##
include Heap_intf.S

##
include Container.S1 with type
'a
t :=
'a
t

Removable augments a heap with the ability to remove elements from the heap in lg(n)
(amortized) time at any point after they have been added.

Heap implementation based on a pairing-heap.

This heap implementations supports an arbitrary element type, via a comparison
function. If you need a heap with elements ordered by integers, then it may be more
efficient to use a `Timing_wheel.Priority_queue`

, which is a heap implementation
specialized to integer keys, and with some other performance differences and usage
restrictions.

type
'a
t

of_sexp and bin_io functions aren't supplied for heaps due to the difficulties in reconstructing the correct comparison function when de-serializing.

val
mem : ?equal:('a -> 'a -> bool) -> 'a t -> 'a -> bool

Checks whether the provided element is there, using polymorphic compare if `equal`

is not provided

val
length : 'a t -> int

val
is_empty : 'a t -> bool

val
iter : 'a t -> f:('a -> unit) -> unit

val
fold : 'a t -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum

`fold t ~init ~f`

returns `f (... f (f (f init e1) e2) e3 ...) en`

, where `e1..en`

are the elements of `t`

val
exists : 'a t -> f:('a -> bool) -> bool

Returns `true`

if and only if there exists an element for which the provided
function evaluates to `true`

. This is a short-circuiting operation.

val
for_all : 'a t -> f:('a -> bool) -> bool

Returns `true`

if and only if the provided function evaluates to `true`

for all
elements. This is a short-circuiting operation.

val
count : 'a t -> f:('a -> bool) -> int

Returns the number of elements for which the provided function evaluates to true.

val
find : 'a t -> f:('a -> bool) -> 'a option

Returns as an `option`

the first element for which `f`

evaluates to true.

val
find_map : 'a t -> f:('a -> 'b option) -> 'b option

Returns the first evaluation of `f`

that returns `Some`

, and returns `None`

if there
is no such element.

val
to_list : 'a t -> 'a list

val
to_array : 'a t -> 'a array

val
min_elt : 'a t -> cmp:('a -> 'a -> int) -> 'a option

Returns a minimum (resp maximum) element from the collection using the provided
`cmp`

function, or `None`

if the collection is empty. In case of a tie, the first
element encountered while traversing the collection is returned. The implementation
uses `fold`

so it has the same complexity as `fold`

.

val
max_elt : 'a t -> cmp:('a -> 'a -> int) -> 'a option

val
min_elt : 'a t -> cmp:('a -> 'a -> int) -> 'a option

Even though these two functions are part of Container.S1, they are documented
separately to make sure there is no confusion. They are independent of the
comparison function used to order the heap. Instead, a traversal of the entire
structure is done using the provided `cmp`

function to find a min or max.

If you want to access the smallest element of the heap according to the heap's
comparison function in constant time, you should use `top`

.

val
max_elt : 'a t -> cmp:('a -> 'a -> int) -> 'a option

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

returns the top (i.e., smallest) element of the heap

val
top_exn : 'a t -> 'a

val
add : 'a t -> 'a -> unit

val
remove_top : _ t -> unit

`remove_top t`

does nothing if `t`

is empty

val
pop : 'a t -> 'a option

This removes and returns the top (i.e. least) element

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.

module
Removable
: sig .. end