CODEWITHSUNDEEP
haskellfunctional-programmingocaml
Ang
Ang

Reputation: 545

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

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!

Upvotes: 12

Views: 3085

Answers (4)

Ta Thanh Dinh
Ta Thanh Dinh

Reputation: 660

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.

Upvotes: 0

Vladimir Kostyukov
Vladimir Kostyukov

Reputation: 2552

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

Upvotes: 2

user593999
user593999

Reputation:

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

Upvotes: 5

Dietrich Epp
Dietrich Epp

Reputation: 213318

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.

Upvotes: 10

Related Questions