5.1-5.txt

structure Dequeue : Queue =
struct
  type a Queue = a list * a list
  val empty = ([], [])
  fun isEmpty (t, r) = null f

  fun len nil = 0
    | length (_ :: y) = 1 + length y;

  fun apart(f, x :: r) = 
      if len(f) >= len(r) then (x :: r, rev f)
      else apart (x :: f, r)

  fun checkfr([], r) = apart([], r)
    | checkfr(f, []) = apart([], rev f)
    | checkfr q = q

  fun cons((f, r), x) = checkfr(x :: f, r)
  fun head ([], _) = raise Empty
    | head (x :: f, r) = x
  fun tail ([], _) = raise Empty
   | tail (x :: f, r) = checkfr (f, r)
   
  fun snoc((f, r), x) = checkf(f, x :: r)
  fun last ([], _) = raise Empty
    | last (f, x :: r) = x
  fun init ([], _) = raise Empty
   | init (f, x :: r) = checkfr (f, r)
   
#  head, last
#  1ステップ + ポテンシャルを1増やす = 2

# cons, snoc
# 空ではない場合は 1ステップ + ポテンシャルを1増やす = 2

# tail, init
# 逆側リストを反転しない場合はステップ1でポテンシャルは±1
# 反転する場合は(|f| - |r| + 1)ステップ実行してポテンシャルは(|f| - |r|)減るので = 1

# 5-2
一つの木は1貯金持つとする
呼び出しは k + 1 ステップかかる
初期状態でt個の木があり、insertの後ではt - k + 1個の木があるので貯金の増減は
(t - k + 1) - t = 1 - k
k + 1ステップで1 - kの貯金の増減があるので 償却コストは2

# 5-3
ランクrの二項木は2^r個の要素を持つ
要素数をmとする
サイズnの二項ヒープは高々[log(n + 1)]個の木しか持たない

merge
ポテンシャル関数φ = 木の数
もともとの木の数 t1 + t2
merge後の木の数 t1 + t2 - k + 1
ポテンシャルの変化量 1 - k
リストの長さ * k


deleteMin
ポテンシャル関数φ = 木の数
もともとの木の数 t
削除後の木の数 t - k + 1
ポテンシャルの変化量 1 - k

* removeMinTreeのコスト
リストの長さ + 1

* revのコスト
リストの長さ + 1

* mergeのコスト


# 5-4
fun smaller(pivot, E) = E
  | smaller(pivot, T (a, x, b)) =
    if x > pivot then smaller (pivot, a)
    else case b of
      E => T (a, x, E)
      | T(b1, y, b2) =>
        if y >= pivot then T (smaller (pivot, b1), x, a)
        else T (smaller (pivot, b1), y, T(b2, x, a))