Pqueue(3) OCaml library Pqueue(3)

# [NAME](#NAME)

Pqueue - Priority queues.

# [Module](#Module)

Module Pqueue

# [Documentation](#Documentation)

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).

**Since** 5.4

*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 :* **(E : OrderedType) -> sig end**

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 :* **(E : OrderedType) -> sig end**

Functor building an implementation of the max-priority queue structure given a totally ordered type for elements.

## [Polymorphic priority queues](#Polymorphic_priority_queues)

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**  
elt that can be compared without depending on the values of **'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 :* **(E : OrderedPolyType) -> sig end**

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 :* **(E : OrderedPolyType) -> sig end**

Functor building an implementation of max-priority queues given a totally ordered type for the elements.

2026-10-23 OCamldoc

---

Document: Pqueue(3o) from ocaml 5.5.2-r0 (Chainguard OS)
Source: https://github.com/ocaml/ocaml