二項ヒープ(未完)

gistfile1.txt

data Tree a = Node a [Tree a] deriving Show
data Digit a = Zero | One (Tree a) deriving Show
data Schedule a = Schedule [[Digit a]] deriving Show
data Heap a = Heap [Digit a] (Schedule a) deriving Show

empty :: Heap a
empty = Heap [] (Schedule [])

isEmpty :: Heap a -> Bool
isEmpty (Heap [] _) = True
isEmpty _           = False

link :: Eq a => Tree a -> Tree a -> Tree a
link t1@(Node x1 c1) t2@(Node x2 c2)
  | x1 == x2  = Node x1 (t2:c1)
  | otherwise = Node x2 (t1:c2)
      
insTree :: Eq a => Tree a -> [Digit a] -> [Digit a]
insTree t []          = One t : []
insTree t (Zero:ds)   = One t : ds
insTree t (One t':ds) = Zero : insTree (link t t') ds

exec :: Schedule a -> Schedule a
exec (Schedule [])                 = Schedule []
exec (Schedule ((Zero:job):sched)) = Schedule (job : sched)
exec (Schedule (_:sched))          = Schedule sched

insert :: Eq a => a -> Heap a -> Heap a
insert x (Heap ds (Schedule sched)) = Heap ds' sched'
  where
    ds' = insTree (Node x []) ds
    sched' = exec . exec . Schedule $ ds':sched

infixl 0 >-
(>-) :: a -> (a -> b) -> b
a >- f = f a