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
of_sexp and bin_io functions aren't supplied for heaps due to the difficulties in reconstructing the correct comparison function when de-serializing.
Checks whether the provided element is there, using polymorphic compare if
is not provided
fold t ~init ~f returns
f (... f (f (f init e1) e2) e3 ...) en, where
are the elements of
true if and only if there exists an element for which the provided
function evaluates to
true. This is a short-circuiting operation.
true if and only if the provided function evaluates to
true for all
elements. This is a short-circuiting operation.
Returns the number of elements for which the provided function evaluates to true.
Returns as an
option the first element for which
f evaluates to true.
Returns the first evaluation of
f that returns
Some, and returns
None if there
is no such element.
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
fold so it has the same complexity as
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
create ?min_size ~cmp returns a new min-heap that can store
without reallocations, using ordering function
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
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
pop operations. Alternating
remove operations can therefore
use unbounded memory.
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.