如何在OCaml中实现一个二进制堆使用列表？ [英] How to implement a binary heap using list in OCaml?

问题描述

我在OCaml中使用list实现了一个二进制堆，只是为了提高我的OCaml技能。

I感觉使用列表非常困难，经过两天的努力之后，我不得不来这里寻求建议和提示。

---

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

显然，我不能使用基于算法的原始数组来实现它使用列表。



我试图利用的是二叉树。我已经保持不变一个节点应该比任何低于它的节点都大。

我粗略地说明了如何实现 insert ，但我不确定它是否正确。

对于二叉树，每个节点都有两个子，值和 size n ，它是 offsprings 它拥有的总数。 n 用于平衡树。

当插入 x ，我比较节点（从根，递归）。假设 x <节点的值，则

如果一个或两个节点的子节点都是 Leaf none ，那么我将 x 插入到那个Leaf的地方。 / code>节点的孩子是Leaf，那么我会选择其中n少的孩子，然后递归插入。

---

这里是我的代码

  type'a heap = 
 | 'a *'堆的节点*'堆* int 
 |叶
 
异常EmptyHeapException 
 
 let create_heap（）= Leaf ;; 
 
让rec插入x =函数
 |叶 - >节点（x，Leaf，Leaf，0）
 |节点（v，l，r，n） - > 
 let（stay，move）= if x> （x，v）else（v，x）
 in 
 match（l，r）with 
 | （叶，叶） - > 
节点（逗留，节点（移动，叶，叶，0），叶，1）
 | （Leaf，_） - > 
 Node（stay，Node（move，Leaf，Leaf，0），r，n + 1）
 | （_，Leaf） - > 
节点（stay，l，Node（move，Leaf，Leaf，0），n + 1）
 | （节点（_，_，_，n1），节点（_，_，_，n2）） - >如果n1 <= n2，则
然后
节点（stay，（insert move l），r，n1 + 1）
 else 
节点（stay，l， ），n2 + 1）;; 
  

---

好的，我有以下问题。

1. 我的方向是否正确？我的想法或实现是否正确？


2. 我在执行 get_top 函数时遇到困难。我不知道如何继续。任何提示？


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

解决方案

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

删除最大元素（根）基本上是一个删除，这总是最困难的。实质上，你需要在保持不变的情况下合并两棵树。我现在没有时间详细研究它，但我认为它会变成可能的。

如果你看看Okasaki（你可以如果你被困住了，你会发现他的树有一个额外的不变性，使得这些操作更容易。我很确定这不是我马上想出来的东西。他的实施基于合并两棵树的操作。它用于插入和删除。

匆匆一瞥电池堆代码基于二叉树，实际上它更加复杂。

更新

冈崎的书纯功能数据结构是他的博士论文的详细阐述。似乎优先级队列只出现在书中 - 对不起。如果你对FP非常感兴趣，并且不太需要现金，那么本书确实值得拥有。

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

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

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

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

这个结构的有用性取决于你能够删除O中的根（记录n ），同时保持这两个不变量。

删除的草图应该是这样的：

  let pop = function Leaf  - > 0 |节点（_，_，_，p） - > p 
 
让rec合并ab = 
（* a，b的数量最多相差一个。pop a> = pop b *）
匹配a，b with 
 |叶，叶 - >叶
 |叶，_  - > b 
 | _，叶子 - > a 
 |节点（av，al，ar，ap），节点（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）
 
和delete_min =函数
 |叶 - >叶
 |节点（_，叶，叶，_） - >叶
 |节点（_，l，叶，_） - > l 
 |节点（_，Leaf，r，_） - > r 
 |节点（_，l，r，_） - > 
 if pop l> = pop r然后merge lr else merge rl 
  

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

更新

作为一个纯粹的脑袋，我从未想过现实生活中的Chris Okasaki是什么样子。他在西点教学，在那里找到他的个人页面并不难。它可能会满足你的一些好奇心。

I am implementing a binary heap using list in OCaml, just to sharpen my OCaml skills.

I feel it very difficult using list and after struggling for 2 days, I have to come here for suggestions and hints.

---

Here is my thought so far

Obviously, I can't use the orignal array based algorithm to implement it using list.

What I am trying to utilise is binary tree. I have keep the invariant that a node should be bigger than any node whose level is lower than its.

I roughly figured out how to implement insert, although I am not sure whether it is correct or not.

For the binary tree, each node has two children, value and size n which is the total number of offsprings it has. This n is used to balance the tree.

When inserting x, I compare with a node (from root, recursively). Assume x < the value of the node, then

If one or both of the node's children are Leaf, then I insert the x to that Leaf place.

If none of the node's children are Leaf, then I will choose the child whose n is less and then recursively insert.

---

Here is my code

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);;

---

Ok, I have following questions.

1. Am I heading to the correct direction? Is my thought or implementation correct?
2. I get stuck in implementing get_top function. I don't know how to continue. any hints?
3. ocaml batteries implemented an efficient batHeap.ml. I have had a look, but I feel its way is totally different from mine and I can't understand it. Any one can help me understanding it?

解决方案

This insertion code looks pretty nice to me. (I was confused by the counts for a while, but now I see they're counting the number of offspring.)

The function to remove the largest element (the root) is basically a deletion, which is always the most difficult. In essence you need to merge two trees while maintaining your invariant. I don't have time right now to work through it in detail, but I think it will turn out to be possible.

If you look in Okasaki (which you can do if you get stuck!) you'll see his trees have an extra invariant that makes it easier to do these operations. I'm pretty sure it's not something I would come up with right away. His implementation is based on an operation that merges two trees. It's used for insertion and deletion.

At a quick glance the Batteries heap code is based on "binomial trees", which are in fact a lot more complicated. They're explained in Okasaki also.

Update

Okasaki's book Purely Functional Data Structures is an elaboration of his PhD thesis. It appears that priority queues appear only in the book--sorry. If you're really interested in FP and not too strapped for cash the book is really worth owning.

As I said, your insert code looks great to me. It seems to me you actually have two invariants:

• The value in a node is less than or equal to the values at the roots of its subtrees (ordering invariant).

• The populations of the subtrees of a node differ by at most 1 (balance invariant).

As I said, I don't have time to verify in detail, but it looks to me like your insert code maintains the invariants and thus is O(log n).

The usefulness of this structure depends on your being able to delete the root in O(log n) while maintaining these two invariants.

The sketch of delete would be something like this:

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

I still don't have a lot of time, so this might need some fixing up for correctness or for complexity.

Update

Being a purely cerebral guy, I (truly) never wondered what Chris Okasaki is like in real life. He teaches at West Point, and it's not too difficult to find his personal page there. It might satisfy some of your curiosity.

这篇关于如何在OCaml中实现一个二进制堆使用列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！