module Priority_queue:Priority queue of unique integer elements.`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.

`e`

in the queue `q`

`c`

, then you `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.

Hosted by the