How to implement a binary heap using list in OCaml?

Question

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.

Am I heading to the correct direction? Is my thought or implementation correct?
I get stuck in implementing get_top function. I don't know how to continue. any hints?
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?

Why don't you just write x > v instead of compare x v > 0? — Andrej Bauer
– Andrej Bauer, Commented Mar 7, 2013 at 2:49
@AndrejBauer yes, you are right. I just initially had the idea that I should have a compare function as a parameter to the heap, sort, etc as some users may not use Pervasives.compare. — Jackson Tale
– Jackson Tale, Commented Mar 7, 2013 at 13:31
I see. In that case you may be interested in using a functor. By the way, did you look at the source code for OCaml Map module in the standard library? It has an implementation of balanced binary search trees, much like what you are implementing. — Andrej Bauer
– Andrej Bauer, Commented Mar 7, 2013 at 13:46
@AndrejBauer thanks. actually i haven't learned functor yet, but will do :D — Jackson Tale
– Jackson Tale, Commented Mar 7, 2013 at 15:02
Why do you say that you're trying to use lists, there are no lists in your code ? — bruce_ricard
– bruce_ricard, Commented Mar 7, 2013 at 18:53

Jeffrey Scofield · Accepted Answer · 2013-03-13 22:20:04Z

3

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.

edited Mar 13, 2013 at 22:20

answered Mar 7, 2013 at 0:22

Jeffrey Scofield

67k2 gold badges77 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Jackson Tale Over a year ago

thanks. what do u mean by Okasaki? you mean cs.cmu.edu/~rwh/theses/okasaki.pdf ? or the book amazon.co.uk/Purely-Functional-Structures-Chris-Okasaki/dp/…?

Jackson Tale Over a year ago

also, despite Okasaki, do you agree with my thought or implementation of insert? any suggestions of improvement?

Jeffrey Scofield Over a year ago

(Like I said, the insert looks good to me. It all hinges on whether you can implement delete_min on your tree. See update.)

Jackson Tale Over a year ago

do you think your merge is logN? and also how about the balance of the tree?

Jeffrey Scofield Over a year ago

Well, I tried. Like I said I don't have time to really check carefully, I figured you might want to do that. I tried to maintain the balance, again you might want to verify this.

|

Collectives™ on Stack Overflow

How to implement a binary heap using list in OCaml?

Here is my thought so far

Here is my code

1 Answer 1

10 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Here is my thought so far

Here is my code

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related