empty returns the empty heap.

is_empty h returns true iff the heap h is empty.

merge h1 h2 merges the two heaps h1 and h2. If one heap is empty, the result is physically equal to the other heap. Complexity: O(log (m+n)) where m and n are the number of elements in each heap.

insert x h inserts an element x into the heap h. Complexity: O(log n) where n is the number of elements in h.

add h x is insert x h.

find_min h returns the minimal element of h, or None if h is empty. Complexity: O(1).

find_min_exn h is akin to find_min, but it raises Empty when the heap is empty.

• raises Empty

  if the heap is empty.

take h returns the minimum element of h and the new heap without this element, or None if h is empty. Complexity: O(log n).

take_exn h is akin to take, but it raises Empty when the heap is empty.

• raises Empty

  if the heap is empty.

size h is the number of elements in the heap h. Complexity: O(n).

delete_one eq x h deletes an occurrence of the value x from the heap h, if there is some. If h does not contain x, then h itself is returned. Elements are identified by the equality function eq. Complexity: O(n).

• since 2.0

delete_all eq x h deletes all occurrences of the value x from the heap h. If h does not contain x, then h itself is returned. Elements are identified by the equality function eq. This function is more efficient than filter because it avoids considering elements greater than x. Complexity: O(n).

• since 2.0

filter p h filters the elements of h, only retaining those that satisfy the predicate p. If no element in h satisfies p, then h itself is returned. Complexity: O(n).

iter f h invokes f on every element of the heap h.

fold f acc h folds on all elements of h.

add_list h l adds the elements of the list l into the heap h. An element occurring several times will be added that many times to the heap. Elements need not be given in any particular order. This function is more efficient than repeated insertions. Complexity: O(log m + n) where m and n are the number of elements in h and l, respectively.

• since 0.16

add_iter h iter is akin to add_list, but taking an iter of elements as input.

• since 2.8

add_seq h seq is akin to add_list, but taking a Seq.t of elements as input. Renamed from add_std_seq since 3.0.

• since 3.0

add_gen h gen is akin to add_list, but taking a gen of elements as input.

• since 0.16

add_iter_almost_sorted h iter is equivalent to merge h (of_iter_almost_sorted iter). See of_iter_almost_sorted. Complexity: O(log m + n).

• since 3.14

of_list l builds a heap from the list of elements l. Elements need not be given in any particular order. This function is more efficient than repeated insertions. It is equivalent to add_list empty l. Complexity: O(n).

of_iter iter is akin to of_list, but taking an iter of elements as input.

• since 2.8

of_seq seq is akin to of_list, but taking a Seq.t of elements as input. Renamed from of_std_seq since 3.0.

• since 3.0

of_gen gen is akin to of_list, but taking a gen of elements as input.

of_iter iter builds a heap from the iter sequence of elements. Elements need not be given in any particular order. However, the heap takes advantage of partial sorting found in the input: the closer the input sequence is to being sorted, the more efficient it is to convert the heap to a sorted sequence. This enables heap-sorting that is faster than O(n log n) when the input is almost sorted. In the best case, when only a constant number of elements are misplaced, then successive take run in O(1), and to_list_sorted runs in O(n). Complexity: O(n).

• since 3.14

to_list h returns a list of the elements of the heap h, in no particular order. Complexity: O(n).

to_iter h is akin to to_list, but returning an iter of elements.

• since 2.8

to_seq h is akin to to_list, but returning a Seq.t of elements. Renamed from to_std_seq since 3.0.

• since 3.0

to_gen h is akin to to_list, but returning a gen of elements.

to_list_sorted h returns the list of elements of the heap h in increasing order. Complexity: O(n log n).

• since 1.1

to_iter_sorted h is akin to to_list_sorted, but returning an iter of elements.

• since 2.8

to_seq_sorted h is akin to to_list_sorted, but returning a Seq.t of elements. Renamed from to_std_seq_sorted since 3.0.

• since 3.0

to_tree h returns a ktree of the elements of the heap h. The layout is not specified. Complexity: O(n).

to_string ?sep f h prints the heap h to a string, using f to convert elements to strings and sep (default: ",") as a separator between elements.

• since 2.7

pp ?pp_start ?pp_stop ?pp_sep ppf h prints h on ppf. Each element is formatted with ppf, pp_start is called at the beginning, pp_stop is called at the end, pp_sep is called between each element. By default, pp_start and pp_stop do nothing, and pp_sep is (fun out -> Format.fprintf out ",@ "). Renamed from print since 2.0

• since 0.16