Module PQueue.HeapImpl

module HeapImpl: PQ

A priority queue implementation using a binary heap

type 'a t

a priority queue containing 'a

val empty : 'a Util.comparator -> 'a t

constructs an empty priority queue, ordered by the given comparator

val insert : 'a -> 'a t -> 'a t

insert x q yields a queue containing x and the elements of q

val remove : 'a t -> ('a * 'a t) option

remove q returns the maximum element of q (according to comparator q) and another queue q' containing the remaining elements

It returns None if the queue is empty.

val max : 'a t -> 'a option

max q returns the maximum element of q (according to comparator q) returns None if the queue is empty.

val size : 'a t -> int

size q returns the number of elements of q

val is_empty : 'a t -> bool

is_empty q returns true if q is empty

val comparator : 'a t -> 'a Util.comparator

comparator q returns the comparator that q is ordered by