title: How to implement a binary heap using list in OCaml?
body: <p>I am implementing a <code>binary heap</code> using list in OCaml, just to sharpen my OCaml skills.</p>
  
  <p>I feel it very difficult using list and after struggling for 2 days, I have to come here for suggestions and hints.</p>
  
  <hr>
  
  <h2>Here is my thought so far</h2>
  
  <p>Obviously, I can't use the orignal <code>array based</code> algorithm to implement it using list. </p>
  
  <p>What I am trying to utilise is <code>binary tree</code>. I have keep the <code>invariant</code> that a node should be bigger than any node whose level is lower than its. </p>
  
  <p>I roughly figured out how to implement <code>insert</code>, although I am not sure whether it is correct or not. </p>
  
  <p>For the binary tree, each node has <code>two children</code>, <code>value</code> and <strong><code>size n</code> which is the total number of <code>offsprings</code> it has</strong>. This <code>n</code> is used to balance the tree.</p>
  
  <p>When inserting <code>x</code>, I compare with a node (from root, recursively). Assume <code>x &lt; the value of the node</code>, then </p>
  
  <p>If one or both of the node's children are <code>Leaf</code>, then I insert the <code>x</code> to that Leaf place.</p>
  
  <p>If <code>none</code> of the node's children are Leaf, then I will choose the child whose n is less and then <code>recursively insert</code>.</p>
  
  <hr>
  
  <h2>Here is my code</h2>
  
  <pre><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 -&gt; Node (x, Leaf, Leaf, 0)
    | Node (v, l, r, n) -&gt;
      let (stay, move) = if x &gt; v then (x, v) else (v, x)
      in 
      match (l, r) with 
        | (Leaf, Leaf) -&gt; 
          Node (stay, Node (move, Leaf, Leaf, 0), Leaf, 1)
        | (Leaf, _) -&gt; 
          Node (stay, Node (move, Leaf, Leaf, 0), r, n+1)
        | (_, Leaf) -&gt;
          Node (stay, l, Node (move, Leaf, Leaf, 0), n+1)
        | (Node (_, _, _, n1), Node (_, _, _, n2)) -&gt;
          if n1 &lt;= n2 then
            Node (stay, (insert move l), r, n1+1)
          else 
            Node (stay, l, (insert move r), n2+1);;
  </code></pre>
  
  <hr>
  
  <p>Ok, I have following questions.</p>
  
  <ol>
  <li>Am I heading to the correct direction? Is my thought or implementation correct?</li>
  <li>I get stuck in implementing <code>get_top</code> function. I don't know how to continue. any hints?</li>
  <li>ocaml batteries implemented an efficient <a href="https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batHeap.ml" rel="nofollow">batHeap.ml</a>. 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?</li>
  </ol>