functional-programming - 如何在 OCaml 中使用列表实现二进制堆？

Question

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

感觉list很难用，折腾了2天，还是来这里求建议和提示。

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

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

我正在尝试使用的是 binary tree .我保留了 invariant一个节点应该大于其级别低于其级别的任何节点。

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

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

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

如果节点的一个或两个子节点是 Leaf ，然后我插入 x到那个叶子的地方。

如 none节点的 child 是叶子，那么我会选择n小的 child 然后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);;

好的，我有以下问题。

我是否朝着正确的方向前进？我的想法或实现是否正确？

我被困在实现 get_top功能。我不知道如何继续。任何提示？

ocaml 电池实现了高效的 batHeap.ml .我看过，但我觉得它的方式和我的完全不同，我无法理解。任何人都可以帮助我理解它吗？

Answer 1

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

删除最大元素(根)的函数基本上是删除，这总是最困难的。本质上，您需要在保持不变性的同时合并两棵树。我现在没有时间详细研究它，但我认为结果是可能的。

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

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

更新

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

我仍然没有很多时间，所以这可能需要一些修正以确保正确性或复杂性。

更新

作为一个纯粹的大脑，我(真的)从没想过克里斯冈崎在现实生活中是什么样的。他在西点军校任教，在那里找到他的个人主页并不难。它可能会满足你的一些好奇心。