module Pqueue:sig
..end
Priority queues.
The Pqueue
module implements a data structure of priority queues,
given a totally ordered type for elements. This is a mutable
data structure. Both min- and max-priority queues are provided.
The implementation uses a heap stored in a dynamic array, and is
therefore reasonably efficient: accessing the minimum
(resp. maximum) element takes constant time, and insertion and
removal take time logarithmic in the size of the priority
queue. Note that of_array
runs in linear time (and thus must be
preferred to repeated insertions with add
).
It is fine to have several elements with the same priority.
Nothing is guaranteed regarding the order in which they will be
popped. However, it is guaranteed that the element returned by
min_elt
(or get_min_elt
) is the one that is removed from the
priority queue by pop_min
(or remove_min
). This is important
in many algorithms, (e.g. when peeking at several priority queues
and then selecting one to remove from).
module type OrderedType =sig
..end
Input signature of the functors Pqueue.MakeMin
and Pqueue.MakeMax
.
module type Min =sig
..end
Output signature of the functor Pqueue.MakeMin
.
module MakeMin:
Functor building an implementation of the min-priority queue structure given a totally ordered type for elements.
module type Max =sig
..end
Output signature of the functor Pqueue.MakeMax
.
module MakeMax:
Functor building an implementation of the max-priority queue structure given a totally ordered type for elements.
The following, more complex functors create polymorphic queues of
type 'a t
, just like other polymorphic containers (lists,
arrays...). They require a notion of "polymorphic elements" 'a
that can be compared without depending on the values of
elt'a
.
One usage scenario is when the user wants to pass priorities
separately from the value stored in the queue. This is done by
using pairs priority * 'a
as elements.
module Prio : OrderedType = ...
module PrioQueue = Pqueue.MakeMinPoly(struct
type 'a t = Prio.t * 'a
let compare (p1, _) (p2, _) = Prio.compare p1 p2
end)
(* for example, we now have: *)
PrioQueue.add: 'a PrioQueue.t -> Prio.t * 'a -> unit
PrioQueue.min_elt: 'a PrioQueue.t -> (Prio.t * 'a) option
module type OrderedPolyType =sig
..end
Input signature of the functors Pqueue.MakeMinPoly
and Pqueue.MakeMaxPoly
.
module type MinPoly =sig
..end
Output signature of the functor Pqueue.MakeMinPoly
.
module MakeMinPoly:
Functor building an implementation of min-priority queues given a totally ordered type for the elements.
module type MaxPoly =sig
..end
Output signature of the functor Pqueue.MakeMaxPoly
.
module MakeMaxPoly:
Functor building an implementation of max-priority queues given a totally ordered type for the elements.