How can I implement a purely functional standard binary heap (ocaml or haskell)?

Question

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!

Quiroz

This isn't really much of a question. You should probably reword it as something like "How can I implement a purely functional binary heap?"--you're much more likely to get useful, insightful answers with this formulation. – Vanvanadate

That depends. Do you expect the purely functional version to use the same kind of structure for the data? Behave the same way for certain operations? If these things are allowed to be different, then can it really be called a "binary heap"? – Connate

There is a great book by Chris Okasaki named Purely Functional Data Structures. Might be worth a look! – Prospector

I would also suggest that if you need a priority queue, to use a self-balancing binary search tree. They are already built in to the standard libraries as Set and Map in OCaml and Haskell. They have the same asymptotic complexity for adding, removing, as binary heaps. – Chartres

Answer 1

You don't need an array to implement a heap, you can implement it as a tree structure.

data Heap t = Node t (Heap t) (Heap t) | Nil

The drawback is that you end up reallocating O(log N) of the nodes for every heap operation, and you won't have any of the cache locality of an imperative array-based implementation. Some operations will be difficult with this structure, but since I don't know what you want to do with the heap I can't point you in a more specific direction.

The reason we have special functional structures like finger trees is to speed up specific operations that you don't normally perform on heaps, like retrieving the leftmost leaf node. You can use many of the same data structures you learned for imperative languages in Haskell with only changes to the ways they are updated.

Picrotoxin

Thanks Dietrich, the operation I want to implement is push down a random new value from the root, just not sure which is the best way to implement this operation in a functional style. – Quiroz

Answer 2

Shameless plug: Braun trees are perfect candidates for a purely functional min-heap (or priority queue).

Sicken

Answer 3

You can look through the ideas described in this paper A Functional Approach to Standard Binary Heaps or in this source Heap.scala.

Mauve

Answer 4

As answered by others, there is a pure functional implementation of standard min-heap proposed in the paper of Vladimir Kostyukov. Following is a reimplementation in F#:

type heap<'t> =
    | Leaf
    | Branch of 't * heap<'t> * heap<'t>

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

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


// push x into the heap hp
let rec insert hp x =
    match hp with
    | Leaf -> Branch(x, Leaf, Leaf)
    | Branch (v, l, r) ->
        let fixroot v l r =
            match l, r with
            | Branch (v', l', r'), _ when v' < v -> Branch(v', Branch(v, l', r'), r)
            | _, Branch (v', l', r') when v' < v -> Branch(v', l, Branch(v, l', r'))
            | _ -> 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 < min v vl -> Branch(vr, l, trickledown v l' r')
    | Branch (vl, l', r'), _ when vl < v -> Branch(vl, trickledown v l' r', r)
    | _ -> Branch(v, l, r)


// build a heap from the array a
let heapify a =
    let rec buildfrom i =
        if i < 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) ->
        let rfloat v l r =
            match r with
            | Branch (v', l', r') -> Branch(v', l, Branch(v, l', r'))
            | _ -> Branch(v, l, r)

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

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

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

    | _ -> failwith "heap empty"

For simplification purposes, the height of a heap is recalculated using function height. In the original version, the heap is decorated with this information, as:

type heap<'t> =
    | Leaf
    | Branch of int * 't * heap<'t> * heap<'t>

The pure functional implementation is not asymptotically less performant than Eytzinger's method (i.e. using array): the runtime complexity of insert, remove, etc. is still O(lg n). But it may not profit from cache property as using array.

Abad