Module Priority_queue

module Priority_queue: sig .. end

type elt = int 

Elements in the queue are integers.

type t 

The type of priority queues.

val create : (elt -> elt -> int) -> t

create c is a new priority queue, where the priority among elements is defined by the comparison function c.

The comparison function c has the same interpretation as that of Pervasives.compare: c x y is 0 if x = y, is negative if x < y, and is positive if x > y.

The comparison function may have limited stateful behavior; you may change the value of c x y as follows:

• The relative priority of values, as defined by the comparison c, may be changed arbitrarily for values that are not members of the queue at the time of the change.
• The relative priority of an individual value in the queue may be raised with respect to some, or all, of the other values.

If the priority of a value e in the queue q might have been raised by a state change in c, then you must reorganize the queue with a call to Priority_queue.promote q e before any other operations on q are performed.

val is_empty : t -> bool

is_empty q holds if and only if the queue q is empty.

val insert : t -> elt -> unit

insert q e inserts element e into the priority queue q, if it is not already a member. If e is already a member of q then no operation is performed.

Note: e must not be negative.

val pop : t -> elt

pop q removes the highest priority from the queue q. This element is no longer a member of q.

Note: Priority_queue.is_empty q must not hold.
Returns element that had the highest priority.

val promote : t -> elt -> unit

promote q e reorganizes the priority queue q to take into account the newly raised priority of element e. If e is not in the heap, then this does nothing.

See Priority_queue.create for information about when this function must be called.

val clear : t -> unit

Removes all elements from the queue.