SplayHeap

SplayHeap.hs

data SplayHeap a = E | T (SplayHeap a) a (SplayHeap a) deriving(Show)

partition pivot E = (E, E)
partition pivot t@(T a x b) =
  if x <= pivot then
             case b of
                  E         -> (t, E)
                  T b1 y b2 -> if y <= pivot then
                                  let (small, big) = partition pivot b2
                                  in (T (T a x b) y small, big)
                               else
                                  let (small, big) = partition pivot b1
                                  in (T a x small, T big y b2)
  else
             case a of 
                  E         -> (E, t)
                  T a1 y a2 -> if y <= pivot then
                                  let (small, big) = partition pivot a2
                                  in (T a1 y small, T big x b)
                               else
                                 let (small, big) = partition pivot a1 
                                 in (small, T big y (T a2 x b))

empty = E
isEmpty E = True
isEmpty _ = False

insert x t = T a x b where 
       (a, b) = partition x t

merge E t = t
merge (T a x b) t = T (merge ta a) x (merge tb b) where
      (ta, tb) = partition x t

findMin E = error "empty heap"
findMin (T E x b) = x
findMin (T a x b) = findMin a

deleteMin E = error "empty heap"
deleteMin (T E x b) = b
deleteMin (T (T E x b) y c) = T b y c
deleteMin (T (T a x b) y c) = T (deleteMin a) x (T b y c)

test0 = insert 1 E :: SplayHeap Int
test1 = insert 2 test0
test2 = insert 3 test1
test3 = insert 4 test2
test4 = insert 5 test3