The index is the path

The spec was a priority queue. You can back one with a list — push appends, pop scans for the maximum — and it'll satisfy the interface just fine. It'll also be $O(n)$ on pop, which on 200,000 elements is slow enough to measure with a stopwatch. So: tree heap.

But before talking about the tree, the choice to make it functional deserves a sentence, because the benchmarks at the end look like a failure if you don't know what they were paying for.

A purely functional priority queue returns a new version of the structure on every push and pop. The old version survives, unmodified, for as long as anything holds a reference to it. That means you can snapshot the queue at any point for free, because "copy" and "keep this reference" are the same operation when nothing mutates. It means passing the queue into a function is safe by construction — OCaml's type system makes mutation impossible, so the version you hold afterward is guaranteed to be the version you started with, not a convention you're trusting someone to follow. It means rollback is just keeping an old binding around. It means concurrent reads require no locks, because racing on something that cannot change is not actually a race.

The imperative array heap doesn't give you any of that. It gives you speed instead. Both are real choices; the point is to know what you're paying for before you read the numbers.

Part I: what the structure already knows

The navigation problem in a tree heap is finding the last node — the bottom-rightmost position in a complete binary tree — without an array index handing it to you for free. I drew trees of different sizes and wrote down the sequence of left/right turns to reach each node from the root. The pattern that came out was 10110011110000: the directions to nodes 2 through 8, which is 0, 1, 00, 01, 10, 11, 000.

That's just binary. The 1-indexed position of any node in a complete binary tree, written in binary, is the path from the root: drop the leading 1, and each subsequent bit is the direction at that depth. 0 left, 1 right. Node 6 is 110: drop the leading 1, read 1 then 0 — right, then left.¹

Since the heap already stores its size, and in a complete tree with $n$ nodes the last node is node $n$, the size doubles as the path-encoding integer. floor_log2(sz) gives the depth of the target, implemented via bit-shifting rather than arithmetic. Then step_right extracts one bit per recursive step:

ocaml
let step_right idx i = ((idx lsr (i - 1)) land 1) = 1

At each level the recursion reads one bit and descends into exactly one subtree. $O(\log n)$ nodes touched, $O(1)$ per step, and nothing precomputed — the direction is read on demand from an integer that was already there.

The reason to get this right first, before profiling anything, is that a correct algorithm with a bad implementation can be improved. A wrong algorithm tends to just stay wrong. The bit-path derivation is the floor; everything that follows is finding out how far above it you can get.

Part II: what the machine tells you

With a working heap, I ran a benchmark: push 200,000 random key-priority pairs, then drain the heap completely. OCaml exposes GC statistics alongside wall time — minor_words (total allocation in the minor heap), promoted_words (objects that survived into the major heap), major_collections (full GC passes). These say things the source code doesn't.

The first profile:

text
time ≈ 0.53s    minor_words ≈ 136M    major_collections ≈ 20

The allocation number is the story. Every push and pop rebuilds an $O(\log n)$ path through the tree — that's expected, that's persistence doing its job. What was not expected was how much each node cost, which came down to this:

ocaml
Node of bintree * (key * int) * bintree

Every node stored a tuple. A tuple is a separate heap object — born when the node is built, dead almost immediately after. Over 200,000 operations with O(log n) path rebuilds each, the minor collector was burning through 136 million words per run on allocations whose entire lifespan was a single operation.

Therefore, I removed it.

ocaml
type bintree =
  | Leaf
  | Node of bintree * key * int * bintree

By flattening the payload into the constructor, you lose out on a bit of clarity with the standard definition of a binary tree, that being trees with a singular thing in it. But tradeoffs are always about giving one thing for another, and in this case the drop from 2 objects per branch to one is more than worth it:

text
time ≈ 0.26s    minor_words ≈ 84.5M    major_collections ≈ 20

Minor allocation down 38%. Promoted words down 48%. Runtime halved. One decision about how a constructor holds its fields, and the machine's workload dropped by half.

After that, GC tuning. A persistent data structure allocates along every update path and then releases those nodes — that's the whole model. The default OCaml minor heap is sized conservatively; on an allocation-heavy workload, a larger minor heap means fewer nodes survive long enough to be promoted, which means fewer major collections. At 32 MB:

text
time ≈ 0.17–0.20s    promoted_words ≈ 1.6–2.4M    major_collections ≈ 3–5

Promotions down 85% from baseline. Major collections from ~20 to 3–5.

The final run compared the functional tree heap against an imperative array heap on the same workload:

text
persistent:  time ≈ 0.19–0.26s    minor_words ≈ 67–100M
array:       time ≈ 0.11–0.15s    minor_words ≈ 0

The array heap is about $1.7\times$ faster and allocates almost nothing after initialization². That gap is exactly what the first section was describing. The persistent heap rebuilds paths rather than mutating in place; the GC collects what the old paths leave behind; the old paths surviving is the whole point. The slowness and the guarantee are not separate phenomena. The $1.7\times$ is the price tag for everything listed in the first three paragraphs, and whether it's worth paying depends entirely on what you need the queue to do.

What the profiler added was the specific number. The rest was already known before I ran a single benchmark.