---
name: "Pqueue"
section: "3o"
platform: "linux"
package: "ocaml"
version: "5.5.0-1"
release: "Arch Linux 2026-11-01"
platforms: ["linux"]
url: "https://new.carta.tech/Pqueue"
---

# Pqueue(3o)

Priority queues.

## NAME

Pqueue - Priority queues.

## Module

Module   Pqueue

## 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

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.