package containers

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

A convenient version of Make that take a TOTAL_ORD instead of a partially ordered module. It allow to directly pass modules that implement compare without implementing leq explicitly

Parameters

module E : TOTAL_ORD

Signature

type elt = E.t
type t
val empty : t

Empty heap.

val is_empty : t -> bool

Is the heap empty?

exception Empty
val merge : t -> t -> t

Merge two heaps.

val insert : elt -> t -> t

Insert a value in the heap.

val add : t -> elt -> t

Synonym to insert.

val filter : (elt -> bool) -> t -> t

Filter values, only retaining the ones that satisfy the predicate. Linear time at least.

val find_min : t -> elt option

Find minimal element.

val find_min_exn : t -> elt

Like find_min but can fail.

  • raises Empty

    if the heap is empty.

val take : t -> (t * elt) option

Extract and return the minimum element, and the new heap (without this element), or None if the heap is empty.

val take_exn : t -> t * elt

Like take, but can fail.

  • raises Empty

    if the heap is empty.

val delete_one : (elt -> elt -> bool) -> elt -> t -> t

Delete one occurrence of a value if it exist in the heap. delete_one eq x h, use eq to find one x in h and delete it. If h do not contain x then it return h.

  • since 2.0
val delete_all : (elt -> elt -> bool) -> elt -> t -> t

Delete all occurrences of a value in the heap. delete_all eq x h, use eq to find all x in h and delete them. If h do not contain x then it return h. The difference with filter is that delete_all stops as soon as it enters a subtree whose root is bigger than the element.

  • since 2.0
val iter : (elt -> unit) -> t -> unit

Iterate on elements.

val fold : ('a -> elt -> 'a) -> 'a -> t -> 'a

Fold on all values.

val size : t -> int

Number of elements (linear complexity).

Conversions

The interface of of_gen, of_seq, of_klist has changed since 0.16 (the old signatures are now add_seq, add_gen, add_klist).

val to_list : t -> elt list

Return the elements of the heap, in no particular order.

val to_list_sorted : t -> elt list

Return the elements in increasing order.

  • since 1.1
val add_list : t -> elt list -> t

Add the elements of the list to the heap. An element occurring several times will be added that many times to the heap.

  • since 0.16
val of_list : elt list -> t

of_list l is add_list empty l. Complexity: O(n log n).

val add_seq : t -> elt sequence -> t
  • since 0.16
val of_seq : elt sequence -> t

Build a heap from a given sequence. Complexity: O(n log n).

val to_seq : t -> elt sequence

Return a sequence of the elements of the heap.

val to_seq_sorted : t -> elt sequence

Iterate on the elements, in increasing order.

  • since 1.1
val add_klist : t -> elt klist -> t
  • since 0.16
val of_klist : elt klist -> t

Build a heap from a given klist. Complexity: O(n log n).

val to_klist : t -> elt klist

Return a klist of the elements of the heap.

val add_gen : t -> elt gen -> t
  • since 0.16
val of_gen : elt gen -> t

Build a heap from a given gen. Complexity: O(n log n).

val to_gen : t -> elt gen

Return a gen of the elements of the heap.

val to_tree : t -> elt ktree

Return a ktree of the elements of the heap.

val to_string : ?sep:string -> (elt -> string) -> t -> string

Print the heap in a string

  • since 2.7
val pp : ?sep:string -> elt printer -> t printer

Printer. Renamed from print since 2.0

  • since 0.16
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