Module BatHeap

Functional heaps over ordered types

Ascribes to:

BatEnum.Enumerable with type 'a enumerable = 'a t

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 Make

module Make (Ord : BatInterfaces.OrderedType) : H with type elem = Ord.t

Functorized heaps over arbitrary orderings. All the functions have the same complexity as the non-functorized versions.