gistfile1.hs

data Heap a = Tree !Int !a (Heap a) (Heap a) | Leaf

empty :: Heap a
empty = Leaf

push :: Heap a -> Int -> a -> Heap a
push tree@(Tree p n l r) p2 n2 =
    if p2 < p
    then Tree p2 n2 tree Leaf
    else Tree p n r (merge (Tree p2 n2 Leaf Leaf) l)
push Leaf p n = Tree p n Leaf Leaf

pop :: Heap a -> Maybe (Heap a, a)
pop (Tree _ n l r) = Just (merge l r, n)
pop Leaf           = Nothing

merge :: Heap a -> Heap a -> Heap a
merge l@(Tree p1 n1 l1 r1) r@(Tree p2 n2 l2 r2) =
    if p1 < p2
    then Tree p1 n1 r1 (merge l1 r)
    else Tree p2 n2 r2 (merge l2 l)
merge l Leaf = l
merge Leaf r = r