Pqueue(3)

💖 Pqueue(3) — priority queues, bestie 💖

okay so this is the Pqueue page from the OCaml library, manual section 3 — and it's literally all about priority queues, no cap. 💅

---

🎀 NAME 🎀

Pqueue — priority queues. That's the whole name section, periodt. ✨

📦 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. 🔥

---

💜✨ this page's footer credits OCamldoc, dated 2026-06-22 — source/version and date, bestie, periodt. ✨💜