Purely Functional Data Structures 写経 3.1 Leftist Heaps

Purely Functional Data Structures

続きです。P17〜P20

まずは Heap の signature から。

class Heap h where
  empty :: Ord a => h a
  isEmpty :: Ord a => h a -> Bool
  insert :: Ord a => a -> h a -> h a
  merge :: Ord a => h a -> h a -> h a
  findMin :: Ord a => h a -> a
  deleteMin :: Ord a => h a -> h a

最小値に対する操作が定義されていますね。

data Ord a => LeftistHeap a = E
                            | T Int a (LeftistHeap a) (LeftistHeap a)
                            deriving (Show)

二分木に Int 型の要素が追加されています。

instance Heap LeftistHeap where
  empty = E

  isEmpty E = True
  isEmpty (T _ _ _ _) = False

  merge h E = h
  merge E h = h
  merge h1@(T _ x a1 b1) h2@(T _ y a2 b2)
    | x <= y    = makeT x a1 $ merge b1 h2
    | otherwise = makeT y a2 $ merge h1 b2
   where
     rank :: Ord a => LeftistHeap a -> Int
     rank E = 0
     rank (T r _ _ _) = r

     makeT :: Ord a => a -> LeftistHeap a -> LeftistHeap a -> LeftistHeap a
     makeT x a b = if rank a >= rank b then T (rank b + 1) x a b
                                       else T (rank a + 1) x b a

empty と isEmpty はさらりと流して merge の実装ですね。rank と makeT という内部関数が定義されています。

ここはじっくり考えないと挙動が掴めませんでした。rank によって子要素を swap させる必要性がある、と。これによってバランスを取ることで merge が O(log n) で実行できるということですね。

  insert a h = merge h $ T 1 a E E

  findMin E = error "Empty"
  findMin (T _ x _ _) = x

  deleteMin E = error "Empty"
  deleteMin (T _ _ a b) = merge a b 

insert と findMin と deleteMin の実装。

insert は 単一ノードをマージすることで実現しているんですね。

で、root が最小の要素になるので、findMin と deleteMin が O(1) になる、と。

2009-04-01 15:40 追記

巻末の Haskell コード、Queue からしか載ってないと思ったらちゃんと Heap も載ってますね。章順では無かった模様。
答え合わせ的に比較してみると、data宣言では Ord 型の制約は必要ないみたいですね。

data LeftistHeap a = E
                   | T Int a (LeftistHeap a) (LeftistHeap a)
                   deriving (Show)

これでOKみたいです。なるほど。insert 時に型制約があるからそれで十分なんですね。

isEmpty も False の場合、わざわざデータコンストラクタを使う必要は無いですね。E 以外の全てが False になるので

  isEmpty E = True
  isEmpty _ = False

これで充分、と。