Building a Leftist Heap CLI in OCaml — It's All merge, a Persistent (Immutable) Priority Queue, and an O(log n) Right Spine

A leftist heap — a persistent (immutable) min-priority queue — as an OCaml CLI, in the style of Okasaki's Purely Functional Data Structures. Two hinges: (1) every operation is built on a single one, merge (insert merges a singleton; delete_min merges the deposed root's two children); (2) the "leftist" invariant keeps each node's right spine at least as short as its left, so merge — which only recurses down right spines — is O(log n), and so are insert and delete_min. Because nodes are immutable, popping builds new heaps and every old version stays valid — persistence for free. A functional-paradigm turn after the imperative Rust/Go/Zig run.

📦 GitHub: https://github.com/sen-ltd/leftist-heap-cli

Why a functional lens

The recent algorithm CLIs were imperative — Rust, Go, Zig. This one shows a
different paradigm: immutability and structural sharing. A leftist heap is a
real data structure (a mergeable priority queue), not a toy, expressed the
functional way.

Integers come from stdin; the operation is an argument (sort | top K |
min | stats):

$ echo "42 17 99 3 58 1 76" | heap sort
sorted (7): 1 3 17 42 58 76 99
original heap unchanged: size=7, min=1 (persistent — pops built new heaps)

Everything is merge

There's no sift-up or sift-down. insert merges a singleton; delete_min merges
the deposed root's two children. The whole structure rests on one recursive
function:

let rec merge h1 h2 =
  match h1, h2 with
  | Leaf, h | h, Leaf -> h
  | Node (_, x, a1, b1), Node (_, y, a2, b2) ->
    if x <= y then make_t x a1 (merge b1 h2)
    else make_t y a2 (merge h1 b2)

let insert x h = merge (Node (1, x, Leaf, Leaf)) h
let delete_min = function
  | Leaf -> None
  | Node (_, x, a, b) -> Some (x, merge a b)

Why it's fast: the leftist invariant

merge only ever recurses down the two heaps' right spines. A leftist heap
keeps every node's right spine at least as short as its left, so those spines are
O(log n) long — and so is merge, and thus insert and delete_min. make_t
enforces it, putting the higher-ranked child on the left and storing the rank
(right-spine length) in the node:

let make_t x a b =
  if rank a >= rank b then Node (rank b + 1, x, a, b)
  else Node (rank a + 1, x, b, a)

A test checks the invariant structurally over 300 random heaps
(rank left >= rank right and rank = rank right + 1 at every node), plus
min-heap ordering and that draining the heap yields a sorted list.

Persistence, for free

Because nodes are never mutated, insert/delete_min return a new heap while
the old one stays intact, sharing most of its structure. heap sort drains a
copy and then reports the original is untouched — you hold "before" and "after"
at once:

(* the same value `h` still answers correctly after a copy was drained *)
check "persistence: original min unchanged" (find_min h = Some 0);
check "persistence: original still sorts fully" (to_sorted_list h = sorted xs);

An imperative heap that sifts an array in place can't give you that surviving
"past version." Persistence is exactly what functional data structures buy you.

Takeaway

A leftist heap builds a mergeable priority queue out of one merge, gets
O(log n) from the leftist invariant, and gets persistence for free from
immutability — a textbook functional data structure. I built it in OCaml to add a
functional axis next to the imperative Rust/Go/Zig entries.

leftist.ml — the heap: merge, insert, delete_min, find_min, of_list, to_sorted_list
main.ml    — CLI: integers on stdin, op (sort/top/min/stats) as an argument
test.ml    — invariants, heapsort, merge, persistence, 300 randomized cases

📦 GitHub: https://github.com/sen-ltd/leftist-heap-cli