読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

PFDSを読む: Binomial Heap

Binomial Heapとは、Binomial Treeというデータ構造を使って作られるヒープです。

ここで、Binomial Treeとは、以下のようなデータ構造です。

  • rankが0であるBinomial Treeは、ただ1つのノードからなるシングルトン
  • r > 0 について、rankがrであるBinomial Treeはr個の子を持ち、それらのrankはそれぞれ0, 1, ..., r - 1

この時、rankがrのBinomial Treeは、ちょうど2^r個の子を持つことになります。

証明:
rankがrのBinomial Treeの要素数a_rとすると、
a_0 = 1
a_r = 1 + \Sigma_{k = 0}^{r - 1}a_k
したがって、
a_{r+1} - a_r = (1 + \Sigma_{k = 0}^{r}a_k) - (1 + \Sigma_{k = 0}^{r - 1}a_k)
= a_r
\therefore a_{r+1} = 2a_r
よって、a_{r} = 2^{r}a_0 = 2^r

この性質は、実際にツリーを見てみるとわかりやすいと思います。

f:id:cloudear8:20170507113403p:plain

Binomial Heapは、同じrankを持たないBinomial Treeのリストとして定義されます。rank rのBinomial Treeの要素数2^r個ですから、二進数と同じ原理で、任意個の要素を持つBinomial Heapを作ることができます。
実際、nを2進数で表した時に\Sigma_{k=0}^{m}d_k2^k (d_k \in \{0, 1\})と表せた場合、d_k = 1となるようなkをrankに持つBinomial Treeがそれぞれ1つずつあれば、それらのツリーの要素数の合計はnに等しくなるはずです。

ちなみに、Binomial Heapの操作自体も二進数のアナロジーのようになっています。

また、この時Binomial Heapが持つBinomial Treeの個数はlog_2(n + 1)個程度となります。

さらに、Binomimal Heapは、リスト内の各Binomial Treeについて、一般的なヒープが持つ性質、すなわち、その根の部分がツリーの中での最小値であるという制約も持ちます。
この制約によって、最小値の検索はヒープの各要素の根を見るだけで済むようになるので、O(logn)の計算量で済むことになります。


それでは、Binomial Heapを実装していきましょう。
最初に完成形のコードを載せておいて、後から個別に解説していきます。

module type ORDERED =
  sig
    type t

    val eq : t -> t -> bool
    val lt : t -> t -> bool
    val leq : t -> t -> bool
  end

module type HEAP =
  sig
    type t
    type elt

    val empty : unit -> t
    val is_empty : t -> bool

    val insert : elt -> t -> t
    val merge : t -> t -> t

    val find_min : t -> elt (* raises Empty if heap is empty *)
    val delete_min : t -> t (* raises Empty if heap is empty *)
  end

module BinomialHeap (Elt : ORDERED) : HEAP with type elt = Elt.t =
  struct
    type elt = Elt.t
    type tree = Node of int * elt * tree list
    type t = tree list

    let link (Node (r, x1, c1) as t1) (Node (_, x2, c2) as t2) =
      if Elt.leq x1 x2 then Node (r + 1, x1, t2 :: c1)
      else Node (r + 1, x2, t1 :: c2)

    let rank (Node (r, _, _)) = r

    let root (Node (_, x, _)) = x

    let empty () = []

    let is_empty = function
      | [] -> true
      | _ -> false

    let rec insert_tree t heap = match heap with
      | [] -> [t]
      | t' :: ts' ->
         if rank t < rank t' then t :: heap
         else insert_tree (link t t') ts'

    let insert x h = insert_tree (Node (0, x, [])) h

    let rec merge ts1 ts2 = match ts1, ts2 with
      | _, [] -> ts1
      | [], _ -> ts2
      | t1 :: ts1', t2 :: ts2' ->
         if rank t1 < rank t2 then t1 :: merge ts1' ts2
         else if rank t2 < rank t1 then t2 :: merge ts1 ts2'
         else insert_tree (link t1 t2) (merge ts1' ts2')

    let rec remove_min_tree : t -> tree * t = function
      | [] -> raise (Failure "remove_min_trees")
      | t :: [] -> (t, [])
      | t :: ts ->
         let (t', ts') = remove_min_tree ts
         in if Elt.leq (root t) (root t') then (t, ts)
            else (t', t :: ts')

    let find_min ts =
      let (t, _) = remove_min_tree ts
      in root t

    let delete_min ts =
      let (Node (_, _, ts1), ts2) = remove_min_tree ts
      in merge (List.rev ts1) ts2
  end

まずはBinomialHeap.tree型です。

    type tree = Node of int * elt * tree list

例によってrankをメモしてあります。
これを利用してヒープ本体であるBinomialTree.t型を定義します。

    type t = tree list

注意しなければならないのは、Binomial Heapは要素のツリーのrankが昇順になっているのに対して、Binomial Treeの子のrankは降順になっているということです。
これは両者の操作方法がそれぞれ違うためです。
Binomial Heapは2進数のアナロジーのような操作を行うため、rankが昇順に、Binomial Treeは子の左端に自分と同じrankのものをくっつけるという動作が頻発するため、降順になっています。

次はこれらに対する操作を定義していきます。まずはlink関数。

    let link (Node (r, x1, c1) as t1) (Node (_, x2, c2) as t2) =
      if Elt.leq x1 x2 then Node (r + 1, x1, t2 :: c1)
      else Node (r + 1, x2, t1 :: c2)

これは2進数でいう半加算器のようなものです。rank rのBinomial Treeを2個合成し、rank (r + 1)のBinomial Treeを生成します。

次にinsert_treeを見てみましょう。

    let rec insert_tree t heap = match heap with
      | [] -> [t]
      | t' :: ts' ->
         if rank t < rank t' then t :: heap
         else insert_tree (link t t') ts'

これは2進のインクリメンタのようなものです。heapの"最下位ビット"にツリーを1つ加え、"繰り上がり"が生じれば"上の桁"にも同じ処理をしていきます。

これを各ビットに適用させることによって、2つのヒープをマージすることができます。

    let rec merge ts1 ts2 = match ts1, ts2 with
      | _, [] -> ts1
      | [], _ -> ts2
      | t1 :: ts1', t2 :: ts2' ->
         if rank t1 < rank t2 then t1 :: merge ts1' ts2
         else if rank t2 < rank t1 then t2 :: merge ts1 ts2'
         else insert_tree (link t1 t2) (merge ts1' ts2')

次にfind_min, delete_minですが、これらを実装するために補助関数delete_min_treeを定義します。

    let rec remove_min_tree : t -> tree * t = function
      | [] -> raise (Failure "remove_min_trees")
      | t :: [] -> (t, [])
      | t :: ts ->
         let (t', ts') = remove_min_tree ts
         in if Elt.leq (root t) (root t') then (t, ts)
            else (t', t :: ts')

各Binomial Treeは根が最小値になっているので、remove_min_treeの返り値の左の値の根が最小値となります。
これを利用してfind_min, delete_minを定義します。

    let find_min ts =
      let (t, _) = remove_min_tree ts
      in root t

    let delete_min ts =
      let (Node (_, _, ts1), ts2) = remove_min_tree ts
      in merge (List.rev ts1) ts2

delete_minの中でts1をrevしているのは、Binomial Treeの子のrankの並びとBinomial Heapの要素のrankの並びが逆順になっているためです。