Home > Uncategorized > Functional Splay heap

Functional Splay heap

Citing from Purely Functional Data Structures, page 52:

Splay trees, perhaps in combination with the ExplicitMin functor, are the fastest known implementation of heaps for most applications that do not depend on persistence and that do not call the merge function.

Here is my F# port:

type SplayHeap<‘a> = E | T of SplayHeap<‘a> * ‘a * SplayHeap<‘a>

 

exception Empty

 

module SplayHeap =

    let empty = E

    let isEmpty = function

        | E -> true

        | _ -> false

    let rec partition pivot = function

        | E -> E, E

        | T(a,x,b) as t ->           

            if x <= pivot then

                match b with

                | E -> t, E

                | T(b1,y,b2) ->

                    if y <= pivot then

                        let small, big = partition pivot b2

                        T(T(a,x,b1),y,small), big

                    else

                        let small, big = partition pivot b1

                        T(a,x,small),T(big,y,b2)

            else

                match a with

                | E -> E, t

                | T(a1,y,a2) ->

                    if y <= pivot then

                        let small, big = partition pivot a2

                        T(a1,y,small),T(big,x,b)

                    else

                        let small, big = partition pivot a1

                        small,T(big,y,T(a2,x,b))

    let insert x t = let a, b = partition x t in T(a,x,b)       

    let rec merge = function

        | E, t -> t

        | T(a,x,b), t ->

            let ta, tb = partition x t           

            T(merge(ta,a), x, merge(tb,b))

    let rec findMin = function

        | E -> raise Empty

        | T(E,x,_) -> x

        | T(a,_,_) -> findMin a

    let rec deleteMin = function

        | E -> raise Empty

        | T(E,x,b) -> b

        | T(T(E,x,b),y,c) -> T(b,y,c)

        | T(T(a,x,b),y,c) -> T(deleteMin a, x, T(b,y,c))

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: