FOP/ex1 - 大久保弘崇

1.1

Fork x a (merge b c)
Fork x (merge a c) b

線形なヒープ2つをmergeするとき、joinがこれらだと結果も線形になる。

1.2

このwikiでは絵がかけないので項の形で示す。
実装を動かすと、以下の結果を得る。
1.

Fork 7 1 (Fork 6 2 (Fork 5 3 (Fork 4 4 (Fork 3 5 (Fork 2 6
 (Fork 1 7 Null Null) Null) Null) Null) Null) Null) Null

2.

Fork 7 1 (Fork 3 3 (Fork 1 7 Null Null) (Fork 1 5 Null Null))
         (Fork 3 2 (Fork 1 6 Null Null) (Fork 1 4 Null Null))

3.

Fork 6 2 (Fork 3 3 (Fork 1 4 Null Null) (Fork 1 7 Null Null))
         (Fork 2 5 (Fork 1 6 Null Null) Null)

3.が図1.2の木からどのようにmergeされて出来上がるのか追ってみるとよい。

1.3

最大回避は、両方の部分木のサイズが大きい方は手を付けず、小さい方の木を組み替える計算をする。線形な場合、小さい方が 0 ということで最高に都合がよい。
逆に、平衡ということは二分木の両方の部分木のサイズがあまり変わらないということで、計算量は最悪の場合へ近づく。

1.4

insertにより生成されてから、joinによる複製で一度も置き換わらず、最も長い期間生存しているのは4を持つノード。
(異論あり)

1.5

左

foldr insert Null [2,1,4,3,6,5,8,9,7]

右

h1 where
  h1 = merge n1 h3
  n1 = insert 2 $ insert 1 Null
  h3 = merge n3 h5
  n3 = insert 4 $ insert 3 Null
  h5 = merge n5 h7
  n5 = insert 6 $ insert 5 Null
  h7 = insert 9 $ insert 8 $ insert 7 Null

後続する本文に関して、これらの木の作り方が「根に近いところに新たなノードを追加し、それ以前に作った部分は保存する」スタイルなので、このような木を構成する計算がO(n)である点が重要。
ねじれヒープで同じ手順でヒープを構成すると、何と同じ形をしたヒープを得る。

1.6×

パス

1.7×

計算量を表す記号についてはWikipedia ランダウの記号 - その他の漸近記法を参照。
Oは上界だけの記号なので、

は

でもある。このトリビアルな解を蹴るために問題文ではわざわざ

としているようだ。
具体的な答えは判らない。

1.8△

前半の実装のみ。特に難しいところはない。目立つところだけ示す。

data (Ord a) => Tree a = Null | Fork a (Tree a) (Tree a) (Tree a)
deleteMin (Fork a b c) = merge a (merge b c) -- マージは2つずつしかできない
join (Fork x a b c) d = Fork x b c (merge a d) -- 順ぐりに。

コメント