2

binary heapOCamlのスキルを磨くために、OCamlに使用リストを実装しています。

リストを使うのはとても難しいと感じており、2日間苦労した後、提案やヒントを得るためにここに来なければなりません。

これが私のこれまでの考えです

明らかに、array basedlistを使用して実装するために元のアルゴリズムを使用することはできません。

私が利用しようとしているのはですbinary tree。私はinvariant、ノードがそのレベルよりも低いノードよりも大きくなければならないことを維持しています。

insert正しいかどうかはわかりませんが、実装方法を大まかに理解しました。

二分木の場合、各ノードにはがあり、two childrenこれはノードの総数です。これは、ツリーのバランスを取るために使用されます。valuesize noffspringsn

を挿入するときx、私はノードと比較します（ルートから、再帰的に）。仮定x < the value of the nodeし、次に

ノードの子の一方または両方がである場合、そのリーフの場所にLeafを挿入します。x

ノードの子の1つがLeafの場合none、nが小さい子を選択してからrecursively insert。

これが私のコードです

type 'a heap = 
  | Node of 'a * 'a heap * 'a heap * int
  | Leaf 

exception EmptyHeapException

let create_heap () = Leaf;;

let rec insert x = function
  | Leaf -> Node (x, Leaf, Leaf, 0)
  | Node (v, l, r, n) ->
    let (stay, move) = if x > v then (x, v) else (v, x)
    in 
    match (l, r) with 
      | (Leaf, Leaf) -> 
        Node (stay, Node (move, Leaf, Leaf, 0), Leaf, 1)
      | (Leaf, _) -> 
        Node (stay, Node (move, Leaf, Leaf, 0), r, n+1)
      | (_, Leaf) ->
        Node (stay, l, Node (move, Leaf, Leaf, 0), n+1)
      | (Node (_, _, _, n1), Node (_, _, _, n2)) ->
        if n1 <= n2 then
          Node (stay, (insert move l), r, n1+1)
        else 
          Node (stay, l, (insert move r), n2+1);;

わかりました、次の質問があります。

  1. 私は正しい方向に向かっていますか？私の考えや実装は正しいですか？
  2. 関数の実装に行き詰まりget_topます。続行する方法がわかりません。ヒントはありますか？
  3. ocamlバッテリーは効率的なbatHeap.mlを実装しました。見てみましたが、自分とは全く違う感じで理解できません。誰かが私がそれを理解するのを手伝ってくれる？
4

1 に答える 1

3

この挿入コードは私にはかなり見栄えがします。（しばらくカウントに戸惑いましたが、今では子孫の数をカウントしているようです。）

最大の要素（ルート）を削除する機能は基本的に削除であり、これは常に最も困難です。本質的には、不変条件を維持しながら2つのツリーをマージする必要があります。今は詳しく説明する時間がありませんが、可能になると思います。

岡崎を見ると（行き詰まったらできる！）、彼の木にはこれらの操作を簡単にする余分な不変量があることがわかります。すぐに思いつくものではないと確信しています。彼の実装は、2つのツリーをマージする操作に基づいています。挿入と削除に使用されます。

一見すると、Batteriesヒープコードは「二項ツリー」に基づいていますが、実際にはもっと複雑です。岡崎でも説明されています。

アップデート

オカサキの著書「純粋関数型データ構造」は、彼の博士論文の詳細です。優先キューは本にのみ表示されているようです。申し訳ありません。あなたが本当にFPに興味があり、現金に縛られすぎていないのなら、この本は本当に所有する価値があります。

私が言ったように、あなたの挿入コードは私には素晴らしく見えます。実際には2つの不変条件があるように思われます。

  • ノードの値は、そのサブツリーのルートの値以下です（順序は不変です）。

  • ノードのサブツリーの母集団は、最大で1だけ異なります（バランス不変）。

私が言ったように、私は詳細に検証する時間がありませんが、あなたの挿入コードは不変条件を維持しているように見えます、したがってO（log n）です。

この構造の有用性は、これら2つの不変条件を維持しながら、O（ log n ）のルートを削除できるかどうかに依存します。

削除のスケッチは次のようになります。

let pop = function Leaf -> 0 | Node (_, _, _, p) -> p

let rec merge a b =
  (* populations of a, b differ by at most one. pop a >= pop b *)
  match a, b with
  | Leaf, Leaf -> Leaf
  | Leaf, _ -> b
  | _, Leaf -> a
  | Node (av, al, ar, ap), Node (bv, bl, br, bp) ->
      if av >= bv then Node (av, merge al ar, b, ap + bp)
      else Node (bv, merge al ar, insert av (delete_min b), ap + bp)

and delete_min = function
  | Leaf -> Leaf
  | Node (_, Leaf, Leaf, _) -> Leaf
  | Node (_, l, Leaf, _) -> l
  | Node (_, Leaf, r, _) -> r
  | Node (_, l, r, _) ->
    if pop l >= pop r then merge l r else merge r l

私はまだ多くの時間を持っていないので、これは正確さや複雑さのためにいくつかの修正が必要かもしれません。

アップデート

純粋に大脳の男である私は、（本当に）クリス・オカサキが実生活でどのようなものか疑問に思ったことはありません。彼はウェストポイントで教えています、そしてそこで彼の個人的なページを見つけることはそれほど難しくありません。それはあなたの好奇心の一部を満足させるかもしれません。

于 2013-03-07T00:22:54.637 に答える