package batteries

You can search for identifiers within the package.

in-package search v0.2.0

A community-maintained standard library extension

Install

Dune Dependency

github.com Readme Edit opam file Versions (14)

Authors

O

OCaml batteries-included team

Maintainers

Sources

v3.7.2.tar.gz

md5=1fd7bddce07cf5d244fc9427f7b5e4d4

sha512=c0f2a0fdc8253e0ea999d8d4c58bfbf32b18d251a2e1d9656bf279de5f01a33e9aabac3af4d95f465f8b671e7711ebd37218043face233340a0c11b08fa62f78

doc/batteries.unthreaded/BatHeap/index.html

Module `BatHeap`Source

Functional heaps over ordered types

Ascribes to:

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

Sourcetype +'a t

Heap of elements that are compared with Pervasives.compare.

Sourceval size : 'a t -> int

Number of elements in the heap. O(1)

Construction

Sourceval empty : 'a t

The empty heap.

Sourceval insert : 'a t -> 'a -> 'a t

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

Sourceval 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

Sourceval merge : 'a t -> 'a t -> 'a t

Merge two heaps. O(log m)

Sourceval find_min : 'a t -> 'a

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

raises Invalid_argument
"find_min" if the heap is empty

Sourceval 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

Sourceval of_list : 'a list -> 'a t

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

Sourceval to_list : 'a t -> 'a list

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

Sourceval elems : 'a t -> 'a list

deprecated
Same as to_list.

Sourceval of_enum : 'a BatEnum.t -> 'a t

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

Sourceval enum : 'a t -> 'a BatEnum.t

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

Printing

Source

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

Sourcemodule type H = sig ... end

The result of Make

Sourcemodule 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.

On This Page

Construction
Operations
Transformation
Printing
Functorized version