Priority Queue — Leftist Heap

Overview

A purely functional priority queue implemented as a leftist min-heap. Unlike imperative heaps (arrays), this one is persistent — every operation returns a new heap while the original is preserved. This makes it safe for concurrent use and enables "undo" for free.

The key insight: everything is built on merge. Insert is merge with a singleton. Delete-min is merge of the two children. This elegant design means one well-crafted function powers the entire API.

Data Type

Each node stores its rank — the length of the rightmost path to a leaf. The leftist property ensures rank(left) ≥ rank(right), keeping the right spine short (O(log n) nodes):

type 'a heap =
  | Empty
  | Node of int * 'a * 'a heap * 'a heap
  (* Node (rank, value, left_child, right_child) *)

Core Operations

Merge — The Heart of Everything

Merge two heaps in O(log n). The smaller root becomes the new root; we recursively merge into the shorter (right) spine:

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

let rec merge cmp h1 h2 =
  match h1, h2 with
  | Empty, h | h, Empty -> h
  | Node (_, x, a1, b1), Node (_, y, _, _) ->
    if cmp x y <= 0 then
      make_node x a1 (merge cmp b1 h2)
    else
      merge cmp h2 h1

Insert & Delete

Both are one-liners built on merge:

let insert cmp x h =
  merge cmp (Node (1, x, Empty, Empty)) h

let delete_min cmp = function
  | Empty -> Empty
  | Node (_, _, left, right) -> merge cmp left right

Bottom-Up Construction

Building a heap from a list can be done in O(n) using pairwise merging instead of O(n log n) repeated insertion:

let from_list_fast cmp lst =
  let singletons = List.map
    (fun x -> Node (1, x, Empty, Empty)) lst in
  (* repeatedly merge pairs until one heap remains *)

Derived Operations

• heap_sort: Build heap + extract all → O(n log n) sort with any comparator
• take_min k: Extract the k smallest elements without destroying the heap
• to_sorted_list: Drain the heap into a sorted list
• is_leftist / is_min_heap: Structural validation (useful for testing)
• print_heap: ASCII tree visualization with rank annotations

Persistence Demo

Every operation creates a new heap — the original is untouched:

let h = from_list compare [5; 3; 8; 1; 7] in
let h2 = insert compare 0 h in
let h3 = delete_min compare h in
(* h still has min=1, h2 has min=0, h3 has min=3 *)
(* All three heaps coexist — no mutation! *)

Output

=== Leftist Min-Heap ===
A purely functional priority queue

--- Building a heap ---
Input: [5; 3; 8; 1; 7; 2; 6; 4]

Size: 8
Depth: 4
Minimum: Some 1
Is leftist: true
Is min-heap: true

--- Sorted extraction ---
Sorted: [1; 2; 3; 4; 5; 6; 7; 8]

--- Persistence (functional data structure) ---
Original min:       Some 1
After insert 0 min: Some 0
After delete min:   Some 2
Original unchanged: [1; 2; 3; 4; 5; 6; 7; 8]

--- Merging heaps ---
Heap A sorted: [10; 20; 30]
Heap B sorted: [5; 15; 25]
Merged sorted: [5; 10; 15; 20; 25; 30]

--- Heap sort ---
Input:       [42; 17; 93; 5; 28; 61; 3; 84; 50; 12]
Sorted asc:  [3; 5; 12; 17; 28; 42; 50; 61; 84; 93]
Sorted desc: [93; 84; 61; 50; 42; 28; 17; 12; 5; 3]

--- Top-K smallest ---
Data: [99; 44; 7; 88; 12; 55; 3; 67; 21; 36]
Top 3 smallest: [3; 7; 12]
Top 5 smallest: [3; 7; 12; 21; 36]

--- Max-heap via custom comparator ---
Max-heap top: Some 8
Descending:   [8; 7; 5; 3; 1]

--- String priority queue ---
Words input: [banana; apple; cherry; date; elderberry]
Alphabetical: [apple; banana; cherry; date; elderberry]
First word: Some apple

Concepts Introduced

• Persistent data structures: Operations create new values instead of mutating — the old heap still exists. This is the functional programming way to handle state.
• Rank annotations: Storing computed properties (rank) in the data type avoids recomputation and enables the leftist invariant.
• Merge-based design: One core operation (merge) powers insert, delete, and construction. This pattern appears throughout functional programming (e.g., monoids).
• Custom comparators: Passing cmp as a parameter enables min-heap, max-heap, and any ordering — same pattern as mergesort.ml.
• Bottom-up construction: Pairwise merging achieves O(n) heap construction — an asymptotic improvement over naive repeated insertion.

Complexity