Priority Queues
In Immutables: Fast and Functional Data Structures

knitr::opts_chunk$set(collapse = TRUE, comment = "#>")
if(requireNamespace("pkgload", quietly = TRUE)) {
  pkgload::load_all(".", quiet = TRUE)
} else if(requireNamespace("Immutables", quietly = TRUE)) {
  library(Immutables)
} else {
  stop("Need either installed 'Immutables' or the 'pkgload' package to render this vignette.")
}

Priority queue basics

priority_queue is a persistent structure that associates elements with priority values, typically numeric or character (string). They provide fast access to elements by min or max priority, and insertion of new elements with given priorities.

All operations are persistent, and return modified copies. Peeking at the min/max returns the stored element (which may be any type), popping returns a list with $value containing the stored element, $priority the priority, and $remaining the rest of the priority queue without those elements.

x <- priority_queue("task_a", "task_b", "task_c", priorities = c(3, 1, 2))
x

peek_min(x)
res <- pop_max(x)

res$value
res$priority
res$remaining

The as_priority_queue() variant builds a queue from a vector or list of elements paired with a priority vector. useful when priorities are already in a separate vector.

q <- as_priority_queue(letters[1:4], priorities = c(3, 1, 2, 1))
q

Priority ties

In the case of multiple identical priorities, peek/pop for min/max return a single element, in their original insertion order. Their "all" counterparts (peek_all_min, pop_all_max, etc.) return two priorities: in $elements the elements peeked/popped and in $remaining the other elements. peek_all_max and pop_all_max behave symmetrically on the maximum-priority tie run.

y <- priority_queue() |>
  insert("Jones", priority = "B") |>
  insert("Smith", priority = "A") |>
  insert("Adams", priority = "A")

peek_min(y)
peek_all_min(y)

res1 <- pop_min(y)
res1$value
res1$priority
res1$remaining

res2 <- pop_all_min(y)

res2$elements
res2$remaining

Priority queues can be converted to R lists with as.list(). The drop_meta parameter defaulting to FALSE controls whether priority values are included.

as.list(res2$elements) |> str()
as.list(res2$elements, drop_meta = TRUE) |> str()

Empty queues

Peek/pop helpers are non-throwing on empty queues, length() allows for empty checking.

empty_q <- priority_queue()
length(empty_q)
peek_min(empty_q)
pop_min(empty_q)

Priority values

min_priority() and max_priority() return the current extrema priority (not the stored element), in O(1) via cached monoid state.

q <- priority_queue("a", "b", "c", priorities = c(3, 1, 2))
min_priority(q)
max_priority(q)
min_priority(priority_queue())  # NULL when empty

Named priorities

Priority queues can carry names, set either at construction or on insert(). Names support read-only indexing via [, [[, and $. This is the only indexing form priority_queue supports. Positional indexing and all replacement forms ([<-, [[<-, $<-) error; cast to as_flexseq() first to mutate.

q <- priority_queue(a = "task-a", b = "task-b", priorities = c(2, 1)) |>
  insert("task-c", priority = 3, name = "c")

q[["b"]]
q[c("a", "c")]

try(q[1])         # positional indexing blocked
try(q$a <- "!!")  # replacement blocked

Transforming, iterating, merging

fapply() maps a function over queue elements while preserving priorities. The function receives (value, priority), or (value, priority, name) if it accepts a third argument — priorities and names are passed in read-only, and the return value replaces the stored element.

q <- priority_queue("alice", "bob", "carol", priorities = c(3, 1, 2))
fapply(q, function(value, priority) toupper(value))

loop() (re-exported from the coro package) walks the queue in priority-ascending order, yielding bare values. Traversal is driven by repeated pop_min(), so full traversal is $O(n \log n)$ ($O(\log n)$ per step); ties within equal priority follow insertion order.

q <- priority_queue("task_a", "task_b", "task_c", priorities = c(3, 1, 2))
loop(for (v in q) print(v))

Use fapply() if your callback needs the priority alongside the value, or cast with as_flexseq() for insertion-order iteration. Plain for (v in q) (without loop()) yields raw finger-tree internals rather than elements — always wrap with loop().

merge(x, y) combines two priority queues into a new one containing every entry from both, in O(log(min(m, n))). The .pq_min / .pq_max monoids recompute automatically on the merged tree, so extremum queries work immediately on the result.

a <- priority_queue("x", "y", priorities = c(5, 1))
b <- priority_queue("z", priorities = 3)
m <- merge(a, b)
length(m)
peek_min(m)
peek_max(m)

Both queues must share the same priority type and monoid set; mismatches error (rather than being silently harmonized). Both inputs are left unmodified.

For full sequence-style operations, cast with as_flexseq(). This returns payload items only; priority metadata and any custom monoids are dropped. To instead obtain a flexseq of entry records (value + priority), compose with as.list().

y <- priority_queue() |>
  insert("Jones", priority = "B") |>
  insert("Smith", priority = "A") |>
  insert("Adams", priority = "A")

as_flexseq(y)
as_flexseq(as.list(y))