Okasaki『Purely Functional Data Structures』style の Leftist Heap（左偏ヒープ） を OCaml の CLI として書いた。永続的（不変）な最小優先度付きキューで、実装の肝は 2 つ: (1) すべての操作がたった 1 つの
mergeの上に立つ（insertは単一要素との merge、delete_minは根の 2 子の merge）、(2) 右スパインを左より短く保つ「左偏」不変条件によりmerge＝insert＝delete_minがすべてO(log n)）。不変なので pop しても元のヒープは無傷——構造共有によるタダの永続性。直近の Rust/Go/Zig（命令型）に対して、関数型パラダイムで幅を出す一手。
📦 GitHub: https://github.com/sen-ltd/leftist-heap-cli
なぜ関数型（OCaml）か
直近のアルゴリズム CLI は Rust・Go・Zig と命令型が続いた。ここでは 不変性と構造共有 という別パラダイムを見せるために OCaml を選んだ。左偏ヒープはおもちゃではなく、マージ可能な優先度付きキューという実用データ構造を、関数型らしく表現できる好例だ。
整数列は stdin から、操作は引数（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)
すべては merge
sift-up も sift-down も無い。insert は単一要素との merge、delete_min は退位した根の 2 子の merge。つまり構造全体がたった 1 つの再帰関数に乗る:
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)
速さの理由: 左偏不変条件
merge は 2 つのヒープの 右スパイン だけを再帰的に下る。左偏ヒープは各ノードの右スパインを左以下の長さに保つので、その長さは O(log n)——ゆえに merge も、insert も delete_min も O(log n)。不変条件は make_t が担保する。ランクの高い子を左に置き、ランク（右スパイン長）をノードに格納する:
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)
テストは 300 個のランダムなヒープに対して不変条件を構造的に検査する（全ノードで rank left >= rank right かつ rank = rank right + 1）。加えて最小ヒープ順序と、ヒープを空にすると整列列が得られること（ヒープソート）も確認する。
永続性はタダ
ノードを一切書き換えないので、insert/delete_min は 新しい ヒープを返し、古いヒープは構造の大半を共有したまま無傷で残る。heap sort はコピーを空にしてから「元は無傷」と報告する——「before」と「after」を同時に手にできる:
(* コピーを空にした後も、同じ値 h は正しく答え続ける *)
check "persistence: original min unchanged" (find_min h = Some 0);
check "persistence: original still sorts fully" (to_sorted_list h = sorted xs);
命令型のヒープ（配列を破壊的に sift する）では、この「過去の版がそのまま生き残る」性質は得られない。永続性は関数型データ構造の強みそのものだ。
まとめ
Leftist Heap は「マージ可能な優先度付きキュー」を たった 1 つの merge で構築し、左偏不変条件 で O(log n) を保証し、不変性で永続性をタダ にする、関数型データ構造の教科書例。言語は OCaml を選び、Rust/Go/Zig の命令型系列に 関数型 の軸を足した。
leftist.ml — ヒープ: merge, insert, delete_min, find_min, of_list, to_sorted_list
main.ml — CLI: 整数は stdin, 操作 (sort/top/min/stats) は引数
test.ml — 不変条件・ヒープソート・merge・永続性・300 ランダムケース