This post describes the F# implementation of the lazy pairing heap from Chris Okasaki’s “Purely functional data structures”.
namespace PurelyFunctionalDataStructures module LazyPairingHeap = type t<'a> = | E | T of 'a * t<'a> * Lazy<t<'a>> let empty = E let isEmpty = function E -> true | _ -> false let singleton x = T(x, E, lazy E) let rec merge t1 t2 = match t1, t2 with | E, h -> h | h, E -> h | T(x, _, _), T(y, _, _) -> if x <= y then link t1 t2 else link t2 t1 and link t1 t2 = match t1, t2 with | T(x, E, m), a -> T(x, a, m) | T(x, b, m), a -> T(x, E, lazy merge (merge a b) (Lazy.force m)) | _ -> failwith "should not get there" let insert x a = merge (singleton x) a let rec contains x = function | E -> false | T (y, a, b) -> x = y || contains x a || contains x (Lazy.force b) let findMin = function | E -> raise Empty | T(x, _, _) -> x let deleteMin = function | E -> raise Empty | T(x, a, b) -> merge a (Lazy.force b) let rec remove x = function | E -> E | T(y, a, b) as t -> if a = x then merge a (Lazy.force b) else T(y, remove x a, lazy remove x (Lazy.force b))
[...] Ortin continues his series on Purely Functional Data Structures with a Lazy Pairing Heap, a Real-time Queue and Bottom-up Merge [...]