package batteries

  1. Overview
  2. Docs
A community-maintained standard library extension

Install 

dune-project
 Dependency

github.com Readme Edit opam file Versions (15)

Authors

  1. O
    OCaml batteries-included team

Maintainers

  1. C
    Cedric Cellier <rixed@happyleptic.org>
  2. F
    Francois Berenger <unixjunkie@sdf.org>
  3. Gabriel Scherer
  4. T
    Thibault Suzanne <thi.suzanne@gmail.com>
  5. S
    Simmo Saan <simmo.saan@gmail.com>

Sources

batteries-3.10.0.tar.gz
md5=b7f3b99f12f21b1da6b6aa13d993206d
sha512=8b7f2479eb0271bcfd9168887c1e4a9a815c512eab3ee61b150fc4dfa9ec803e4f73115155f20b3017e4a822148d0e6d1c1e8e5f96790fd691b419dd39a908a2

doc/batteries.unthreaded/BatHeap/index.html

Module BatHeapSource

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)

Sourceval del_min : 'a t -> 'a t

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

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

Sourceval 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

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