package batteries

  1. Overview
  2. Docs
package batteries
Legend:
Library
Module
Module type
Parameter
Class
Class type

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)

val del_min : 'a t -> 'a t

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

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.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct