# Functor Cf_sbheap.Heap

    module Heap: functor (E : Cf_ordered.Total_T) -> Cf_heap.T  with module Element = E

A functor that produces a module of type `Cf_heap` to represent heaps with the element type described by `E`.

Parameters:

`E` | : | `Cf_ordered.Total_T`

    type t

The heap type

    module Element: sig .. end

A module defining the type of the element.

    val nil : t

The empty heap.

    val empty : t -> bool

Use `empty h` to test whether the heap `h` is empty.

    val size : t -> int

Use `size h` to count the number of elements in the heap `h`. Runs in O(n) time and O(log N) space.

    val head : t -> Element.t

Use `head h` to obtain the element on the top of the heap `h`. Raises `Not_found` if the heap is empty.

    val tail : t -> t

Use `tail h` to obtain the heap produced by discarding the element on the top of heap `h`. If `h` is the empty heap, then the empty heap is returned.

    val pop : t -> (Element.t * t) option

Use `pop h` to obtain the head and the tail of a heap `h` in one operation. Returns `None` if the `h` is empty.

    val put : Element.t -> t -> t

Use `put e h` to obtain a new heap that is the result of inserting the element `e` into the heap `h`.

    val merge : t -> t -> t

Use `merge h1 h2` to obtain a new heap that is the result of merging all the elements of `h1` and `h2` into a single heap.

    val iterate : (Element.t -> unit) -> t -> unit

Use `iterate f h` to apply `f` to every element in the heap `h` in an arbitrary order (not top to bottom). Runs in O(n) time and O(1) space.

    val predicate : (Element.t -> bool) -> t -> bool

Use `predicate f h` to test whether all the elements in heap `h` satisfy the predicate function `f`. Runs in O(n) time (with a short cut when an element is found to fail the predicate) and O(1) space. Visits the elements in the heap in arbitrary order (not top to bottom).

    val fold : ('b -> Element.t -> 'b) -> 'b -> t -> 'b

Use `fold f s h` to produce the result of folding a value `s` into the elements of heap `h` with the folding function `f` in an arbitrary order (not top to bottom). Runs in O(n) time and O(1) space.

    val filter : (Element.t -> bool) -> t -> t

Use `filter f h` to apply `f` to each element in the heap `h` in an arbitrary order (not to top bottom), and produce a new heap that contains only those elements for which `f pair` returned `true`.

    val partition : (Element.t -> bool) -> t -> t * t

Use `partition f h` to obtain a pair of new heaps that are the result of applying the partitioning function `f` to each element in the heap `h` in an arbitrary order (not top to bottom). The first heap returned will contain all the elements for which `f pair` returned true, and the second heap will return all the remaining elements.

    val of_seq : Element.t Cf_seq.t -> t

Use `of_seq z` to construct a heap from a sequence of elements. Evaluates the whole sequence. Runs in O(n) time and O(1) space.

    val of_list : Element.t list -> t

Use `of_list s` to construct a heap from a list of elements. Runs in O(n) time and O(1) space.

    val to_seq : t -> Element.t Cf_seq.t

Use `to_seq h` to produce a sequence of elements in top to bottom order from the heap `h`.

    val to_seq2 : t -> (Element.t * t) Cf_seq.t

Use `to_seq2 h` to produce a sequence of elements from the heap `h` where the first element of each pair is a key-value pair obtained from the head of the heap, and the second element of the pair is the corresponding tail of the heap.