Pasted

-- The basic heap data structure
data Heap a
  = E
  | H a [Heap a]
  deriving (Show)
 
extractMin :: Ord a => Heap a -> Maybe (a, Heap a)
extractMin E = Nothing
extractMin h@(H t _) = Just (t, deleteMin h)
 
isEmpty :: Heap a -> Bool
isEmpty E = True
isEmpty _     = False
 
findMin :: Ord a => Heap a -> Maybe a
findMin (H h _) = Just h
findMin E      = Nothing
 
merge :: Ord a => Heap a -> Heap a -> Heap a
merge E h = h
merge h E = h
merge h1@(H x hs1) h2@(H y hs2)
  | x < y = H x (h2 : hs1)
  | otherwise = H y (h1 : hs2)
 
mergePairs :: Ord a => [Heap a] -> Heap a
mergePairs []         = Empty
mergePairs [h]        = h
mergePairs (h1:h2:hs) = merge (merge h1 h2) (mergePairs hs)
 
insert :: Ord a => a -> Heap a -> Heap a
insert x = merge (H x [])
 
deleteMin :: Ord a => Heap a -> Heap a
deleteMin (H _x hs) = mergePairs hs
deleteMin E        = error "heap is empty: invalid operation deleteMin"