skew1.hs

data Skew a = Empty | Node a (Skew a) (Skew a)
 
singleton x = Node x Empty Empty
 
union t1 Empty = t1
union Emtpy t2 = t2
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 heap = union (singleton x) heap
 
extractMin Empty = Nothing
extractMin (Node x l r) = Just (x, union l r)