module SkewHeap(Heap, empty, isEmpty, insert, extractMin, union) where

empty      :: Ord a => Heap a
isEmpty    :: Ord a => Heap a -> Bool
insert     :: Ord a => a -> Heap a -> Heap a
extractMin :: Ord a => Heap a -> (a, Heap a)
union      :: Ord a => Heap a -> Heap a -> Heap a

data Heap a = Empty | Node a (Heap a) (Heap a)
  deriving Show
 
union Empty t2    = t2
union t1    Empty = t1
union (t1@(Node x1 l1 r1)) (t2@(Node x2 l2 r2))
   | x1 <= x2     = Node x1 (union t2 r1) l1
   | otherwise    = Node x2 (union t1 r2) l2
 
insert x t = union (Node x Empty Empty) t
 
extractMin (Node x l r) = (x, union l r)

empty = Empty

isEmpty Empty = True
isEmpty _     = False