<p>As answered by others, there is a pure functional implementation of standard min-heap proposed in <a href="https://arxiv.org/abs/1312.4666" rel="nofollow noreferrer">the paper</a> of Vladimir Kostyukov. Following is a reimplementation in F#:</p>
<pre><code>type heap&lt;'t&gt; =
    | Leaf
    | Branch of 't * heap&lt;'t&gt; * heap&lt;'t&gt;

let rec height hp =
    match hp with
    | Branch (_, l, r) -&gt; 1 + max (height l) (height r)
    | _ -&gt; 0

let rec iscomplete hp =
    match hp with
    | Branch (_, l, r) -&gt; iscomplete l &amp;&amp; iscomplete r &amp;&amp; height l = height r
    | _ -&gt; true


// push x into the heap hp
let rec insert hp x =
    match hp with
    | Leaf -&gt; Branch(x, Leaf, Leaf)
    | Branch (v, l, r) -&gt;
        let fixroot v l r =
            match l, r with
            | Branch (v', l', r'), _ when v' &lt; v -&gt; Branch(v', Branch(v, l', r'), r)
            | _, Branch (v', l', r') when v' &lt; v -&gt; Branch(v', l, Branch(v, l', r'))
            | _ -&gt; Branch(v, l, r)

        if height l = height r then
            if iscomplete r then
                fixroot v (insert l x) r
            else
                fixroot v l (insert r x)
        else if iscomplete l then
            fixroot v (insert l x) r
        else
            fixroot v l (insert r x)


let rec trickledown v l r =
    match l, r with
    | Branch (vl, _, _), Branch (vr, l', r') when vr &lt; min v vl -&gt; Branch(vr, l, trickledown v l' r')
    | Branch (vl, l', r'), _ when vl &lt; v -&gt; Branch(vl, trickledown v l' r', r)
    | _ -&gt; Branch(v, l, r)


// build a heap from the array a
let heapify a =
    let rec buildfrom i =
        if i &lt; Array.length a then
            trickledown a.[i] (buildfrom (2 * i + 1)) (buildfrom (2 * i + 2))
        else
            Leaf

    buildfrom 0


// pop and rebuild the heap hp
let rec remove hp =
    match hp with
    | Branch (x, l, r) -&gt;
        let rfloat v l r =
            match r with
            | Branch (v', l', r') -&gt; Branch(v', l, Branch(v, l', r'))
            | _ -&gt; Branch(v, l, r)

        let lfloat v l r =
            match l with
            | Branch (v', l', r') -&gt; Branch(v', Branch(v, l', r'), r)
            | _ -&gt; Branch(v, l, r)

        let rec merge l r =
            if height l = height r then
                match r with
                | Branch (v, l', r') -&gt; rfloat v l (merge l' r')
                | _ -&gt; Leaf
            else
                match l with
                | Branch (v, l', r') -&gt; lfloat v (merge l' r') r
                | _ -&gt; Leaf

        match merge l r with
        | Branch (v, l', r') -&gt; (x, trickledown v l' r')
        | _ -&gt; (x, Leaf)

    | _ -&gt; failwith &quot;heap empty&quot;
</code></pre>
<p>For simplification purposes, the height of a heap is recalculated using function <code>height</code>. In the original version, the heap is decorated with this information, as:</p>
<pre><code>type heap&lt;'t&gt; =
    | Leaf
    | Branch of int * 't * heap&lt;'t&gt; * heap&lt;'t&gt;
</code></pre>
<p>The pure functional implementation is not asymptotically less performant than Eytzinger's method (i.e. using array): the runtime complexity of <code>insert</code>, <code>remove</code>, etc. is still <code>O(lg n)</code>. But it may not profit from cache property as using array.</p>
How can I implement a purely functional standard binary heap (ocaml or haskell)?
<p>Are there any implementations of a purely functional standard binary heap? I know there are lots of interesting heaps eg: Binomial, leftist heap, they all have functional implementation, just wonder is there a way to implement standard binary heap or we have to use Array to implement it, because of the immutable type ? Thanks!</p>