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)
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
.
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)
Invalid_argument
"find_min"
if the heap is emptyval del_min : 'a t -> 'a t
Delete the minimal element of the heap. O(log n)
Invalid_argument
"del_min"
if the heap is emptyval 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
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
.
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)
module type H =sig
..end
The result of BatHeap.Make
module Make:
Functorized heaps over arbitrary orderings.