最大回避ヒープ。この章ではjoinの仕方を色々工夫する。他にラウンドロビンヒープとかねじれヒープなどがある。

data Ord a => Tree a = Null | Fork Int a (Tree a) (Tree a) deriving (Show)

isEmpty :: Ord a => Tree a -> Bool
isEmpty Null = True
isEmpty (Fork n x a b) = False

minElem :: Ord a => Tree a -> a
minElem (Fork n x a b) = x

deleteMin :: Ord a => Tree a -> Tree a
deleteMin (Fork n x a b) = merge a b

insert :: Ord a => a -> Tree a -> Tree a
insert x a = merge (Fork 1 x Null Null) a

merge :: Ord a => Tree a -> Tree a -> Tree a
merge a Null = a
merge Null b = b
merge a b
          | minElem a <= minElem b = join a b
          | otherwise              = join b a

join (Fork n x a b) c = Fork (n + size c) x aa (merge bb cc)
                        where (aa,bb,cc) = orderBySize a b c

orderBySize a b c
            | size a == biggest = (a,b,c)
            | size b == biggest = (b,a,c)
            | size c == biggest = (c,a,b)
    where
      biggest = size a `max` size b `max` size c

size Null = 0
size (Fork n x a b) = n

関数プログラミングの楽しみ

オーム社 / ￥ 4,410 ()
在庫あり。

いきなり最初の章から面白い。

*Main> insert 5 $ insert 4 $ insert 3 $ insert 2 $ insert 1 Null Fork 5 1 (Fork 2 3 (Fork 1 4 Null Null) Null) (Fork 2 2 (Fork 1 5 Null Null) Null)