Module Heap_intf

module Heap_intf: sig .. end

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

module type S = sig .. end

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

Mutation of the heap during iteration is not supported, but there is no check to prevent it. The behavior of a heap that is mutated during iteration is undefined.

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