Module Batteries.Heap

`module Heap: `BatHeap``

`type `+'a` t `

Heap of elements that are compared with `Pervasives.compare`.

`val size : `'a t -> int``

Number of elements in the heap. O(1)

Construction
`val empty : `'a t``

The empty heap.

`val insert : `'a t -> 'a -> 'a t``

Insert an element into the heap. Duplicates are kept. O(log m)

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

`add x h` is the same as `insert h x`. This function is intended to be used with `fold_right`.

Operations
`val merge : `'a t -> 'a t -> 'a t``

Merge two heaps. O(log m)

`val find_min : `'a t -> 'a``

Find the minimal element of the heap. O(1)

• Raises `Invalid_argument` `"find_min"` if the heap is empty
`val del_min : `'a t -> 'a t``

Delete the minimal element of the heap. O(log n)

• Raises `Invalid_argument` `"del_min"` if the heap is empty
Transformation
`val of_list : `'a list -> 'a t``

Build a heap from a given list. O(n log n)

`val to_list : `'a t -> 'a list``

Enumerate the elements of the heap. O(n log n)

`val elems : `'a t -> 'a list``
Deprecated.Same as `to_list`.
`val of_enum : `'a BatEnum.t -> 'a t``

Build a heap from an enumeration. Consumes the enumeration. O(n log n)

`val enum : `'a t -> 'a BatEnum.t``

Enumerate the elements of the heap in heap order. O(log n) per `BatEnum.get`.

Printing
`val print : `?first:string ->       ?last:string ->       ?sep:string -> ('a, 'b) BatIO.printer -> ('a t, 'b) BatIO.printer``

Print the contents of the heap in heap order. O(n log n)

Functorized version
`module type H = `sig` .. `end``

The result of `BatHeap.Make`

`module Make: `functor (``Ord`` : ``BatInterfaces.OrderedType``) -> ``H``  with type elem = Ord.t``

Functorized heaps over arbitrary orderings.