2

我binary heap在 OCaml 中实现了一个使用列表，只是为了提高我的 OCaml 技能。

使用list感觉很吃力，苦苦挣扎了2天，不得不来这里寻求建议和提示。

到目前为止，这是我的想法

显然，我不能使用原始array based算法使用 list 来实现它。

我试图利用的是binary tree. 我一直invariant认为一个节点应该大于任何级别低于其的节点。

我大致想出了如何实现insert，虽然我不确定它是否正确。

对于二叉树，每个节点都有two children，value而它size n的总数是offsprings。这n用于平衡树。

插入时x，我与一个节点（从根，递归）进行比较。假设x < the value of the node，那么

如果节点的一个或两个子节点是Leaf，那么我将 插入x到那个 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

这个插入代码对我来说看起来很不错。（我有一段时间对计数感到困惑，但现在我看到他们正在计算后代的数量。）

删除最大元素（根）的功能基本上是删除，这始终是最困难的。本质上，您需要在保持不变性的同时合并两棵树。我现在没有时间详细研究它，但我认为这将是可能的。

如果您查看冈崎（如果您遇到困难，您可以这样做！），您会看到他的树有一个额外的不变量，可以更轻松地执行这些操作。我很确定这不是我马上想出来的。他的实现基于合并两棵树的操作。它用于插入和删除。

快速浏览一下，电池堆代码基于“二叉树”，实际上要复杂得多。冈崎也有说明。

更新

Okasaki 的书Purely Functional Data Structures是他博士论文的详细阐述。似乎优先级队列只出现在书中——对不起。如果你真的对 FP 感兴趣，并且不缺钱，那么这本书真的值得拥有。

正如我所说，您的插入代码对我来说看起来很棒。在我看来，您实际上有两个不变量：

  • 节点中的值小于或等于其子树根部的值（排序不变）。

  • 一个节点的子树的种群最多相差 1（平衡不变）。

正如我所说，我没有时间详细验证，但在我看来，您的插入代码维护了不变量，因此是 O( log n )。

这种结构的有用性取决于您能够在保持这两个不变量的同时删除 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 回答