package intPQueue

  1. Overview
  2. Docs
A fast and compact priority queue with low integer priorities

Install 

dune-project
 Dependency

github.com Edit opam file Versions (2)

Authors

  1. F
    François Pottier <francois.pottier@inria.fr>

Maintainers

  1. F
    François Pottier <francois.pottier@inria.fr>

Sources

20250925.tar.gz
md5=4083a2898648f400d470671a71077c1b
sha512=d0ded93af26124ac551391e65eab1773db4524326d8a5c3ebdb2b92ec96878b13b456a08ac593aa27a506023030c7dc78fe48d44483dc987a34887c481b655c6

doc/intPQueue/IntPQueue/Plain/index.html

Module IntPQueue.PlainSource

This is a priority queue whose keys are low nonnegative integers.

This queue is optimized for throughput, that is, speed. When an element is extracted out of the queue, the queue may retain a pointer to this element. This creates a memory leak: that is, the existence of this pointer can prevent the garbage collector from freeing this element. In practice, we do not expect this to be a problem, especially in scenarios where the queue itself is not long-lived.

Sourcetype priority = int

A priority is a nonnegative integer.

Sourcetype 'a t

A priority queue is an abstract mutable data structure. It can be thought of as a bag of elements, where each element carries a certain priority.

Sourceval create : unit -> 'a t

create() creates an empty priority queue.

Time complexity: O(1).

Sourceval add : 'a t -> 'a -> priority -> unit

add q x i inserts the element x with priority i into the queue q.

Time complexity: O(1) (amortized).

Sourceval extract : 'a t -> 'a option

extract q extracts an element out of the queue q and returns it. This element has minimum priority among all of the elements that are currently present in the queue. If the queue is empty, None is returned.

Time complexity: O(p). If the queue is used in a monotonic manner (that is, if the priority that is used in every call to add is at least as high as the priority of the last element that was returned by extract) then the time complexity of n calls to extract is only O(n+p). Indeed, in this monotonic scenario, the cost of scanning the queue's main array, so as to find the next element with minimum priority, is shared between all invocations of extract.

Sourceval extract' : 'a t -> ('a * priority) option

extract' q extracts an element out of the queue q and returns a pair of this element and its priority. This element has minimum priority among all of the elements that are currently present in the queue. If the queue is empty, None is returned.

Time complexity: see extract.

Sourceval is_empty : 'a t -> bool

is_empty q tests whether the queue q is empty.

Time complexity: O(1).

Sourceval cardinal : 'a t -> int

cardinal q returns the number of elements in the queue q.

Time complexity: O(1).

Sourceval repeat : 'a t -> ('a -> unit) -> unit

repeat q f repeatedly extracts an element with minimum priority out of q and passes it to f (which may insert new elements into q), until q is exhausted.

Time complexity: the total cost of n calls to extract and n invocations of the function f.

Sourceval reset : 'a t -> unit

reset q empties the queue q, freeing up the space that the queue occupies in memory. The queue q becomes identical to a queue that has just been created by create.

Time complexity: O(1).