leftist-heap pfds ex3.2

leftist-heap.hs

data LeftistHeap  a = E | T Int a (LeftistHeap a) (LeftistHeap a)
  deriving(Show)

rank E = 0
rank (T r _ _ _) = r

makeT x a b = if rank a >= rank b
                then T (rank b + 1) x a b
                else T (rank a + 1) x b a

merge h E = h
merge E h = h
merge h1@(T _ x a1 b1) h2@(T _ y a2 b2) =
  if x <= y
    then makeT x a1 (merge b1 h2)
    else makeT y a2 (merge h1 b2)

deleteMin (T _ x a b) = merge a b

-- insert x h = merge (T 1 x E E) h

-- ex 3.2
insert x E = T 1 x E E
insert x h@(T n y a b) 
  | rankA == rankB = T n minX (insert nextX a) b
  | otherwise = T (rankB + 1) minX a (insert nextX b)
  where
    rankA = rank a
    rankB = rank b
    (minX, nextX) = if x < y then (x,y) else (y,x)


test0 = insert 5 E
test1 = insert 7 test0
test2 = insert 3 test1
test3 = insert 8 test2
test4 = insert 9 test3
test5 = insert 10 test4