## Functional Splay heap

Citing from Purely Functional Data Structures, page 52:

Splay trees, perhaps in combination with the ExplicitMin functor, are the fastest known implementation of heaps for most applications that do not depend on persistence and that do not call the merge function.

Here is my F# port:

type SplayHeap<‘a> = E | T of SplayHeap<‘a> * ‘a * SplayHeap<‘a>

exception Empty

module SplayHeap =

let empty = E

let isEmpty = function

| E -> true

| _ -> false

let rec partition pivot = function

| E -> E, E

| T(a,x,b) as t ->

if x <= pivot then

match b with

| E -> t, E

| T(b1,y,b2) ->

if y <= pivot then

let small, big = partition pivot b2

T(T(a,x,b1),y,small), big

else

let small, big = partition pivot b1

T(a,x,small),T(big,y,b2)

else

match a with

| E -> E, t

| T(a1,y,a2) ->

if y <= pivot then

let small, big = partition pivot a2

T(a1,y,small),T(big,x,b)

else

let small, big = partition pivot a1

small,T(big,y,T(a2,x,b))

let insert x t = let a, b = partition x t in T(a,x,b)

let rec merge = function

| E, t -> t

| T(a,x,b), t ->

let ta, tb = partition x t

T(merge(ta,a), x, merge(tb,b))

let rec findMin = function

| E -> raise Empty

| T(E,x,_) -> x

| T(a,_,_) -> findMin a

let rec deleteMin = function

| E -> raise Empty

| T(E,x,b) -> b

| T(T(E,x,b),y,c) -> T(b,y,c)

| T(T(a,x,b),y,c) -> T(deleteMin a, x, T(b,y,c))