Functor Heap.MinMaxHeap (.ml)

module MinMaxHeap: functor (Ord : OrderedType) -> sig .. end

An imperative array based min-max heap data structure. Adding elements and removing the minimum and maximum element have logarithmic complexity.

See: Atkinson, Sack, Santoro, Strothotte Mix-Max Heaps and Generalized Priority Queues. Communications of the ACM 1986, October 26, Volume 29, Number 10, p.996-1000

The heap can take up to Sys.max_array_length elements.

Parameters:

Ord : OrderedType

type data = Ord.t

type t

the heap

val create : data -> t

creates an empty heap. null element must be provided.

val add : t -> data -> unit

adds an element.
Raises OVERFLOW if the heap is full.

val min : t -> data

returns the minimum element.
Raises Not_found if the heap is empty.

val max : t -> data

returns the maximum element.
Raises Not_found if the heap is empty.

val remove_min : t -> data

removes the minimum element and returns it.
Raises Not_found if the heap is empty.

val remove_max : t -> data

removes the maximum element and returns it.
Raises Not_found if the heap is empty.

val iter : (data -> unit) -> t -> unit

iterates over all elements (in unsorted order).

val is_empty : t -> bool

no elements?

val size : t -> int

number of elements.

val to_string : t -> string

string representation of the heap as an array