bheap

Priority queues
IN THIS PACKAGE
Module Binary_heap . Make

Parameters

module X : Ordered

Signature

type t

Type of priority queues.

val create : dummy:X.t -> int -> t

create ~dummy c creates a new heap, with initial capacity of c. The value dummy is used to fill unused cells of the internal array. Note: dummy can still be used as a regular value in the queue.

val length : t -> int

length h returns the number of elements of h

val is_empty : t -> bool

is_empty h checks the emptiness of h

val add : t -> X.t -> unit

add x h adds a new element x in heap h; size of h is doubled when maximum capacity is reached; complexity $O(log(n))$

val minimum : t -> X.t

minimum h returns the minimum element of h; raises Empty when h is empty; complexity $O(1)$

val remove : t -> unit

remove h removes the minimum element of h; raises Empty when h is empty; complexity $O(log(n))$

val pop_minimum : t -> X.t

pop_minimum h removes the minimum element of h and returns it; raises Empty when h is empty; complexity $O(log(n))$

val iter : ( X.t -> unit ) -> t -> unit

usual iterators and combinators; elements are presented in arbitrary order

val fold : ( X.t -> 'a -> 'a ) -> t -> 'a -> 'a