Friday, April 9, 2010

Generic Binary Heap

I'm pretty sure I'm going to need a priority queue for my A* search, so I decided to code a generic heap class in F#. The F# code below is largely a translation from Robert Sedgewick's Algorithms in C (Parts 1-4). I tested it pretty thoroughly, but I want to test it a bit more, and I might make a few changes here and there. For the near future, at least, it's designed to be an internal component, so error-reporting, etc. are minimal.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)
type BinaryHeap<'a> (less:'a->'a->bool,
size:int,
resize:int) =

let mutable cursor = 0

let mutable aa :'a array=
Array.zeroCreate (max size 1)

let swap i j =
aa.[0] <- aa.[i]
aa.[i] <- aa.[j]
aa.[j] <- aa.[0]

let incCursor () =
cursor <- cursor+1
if cursor>=aa.Length then
aa <-
Array.append
aa
(Array.zeroCreate (max resize 1))

let rec downHeap i =
let left = i*2
if (left<=cursor) then
let largest =
match (left<cursor) &&
(less aa.[left] aa.[left+1]) with
| true -> left+1
| false -> left
if (less aa.[i] aa.[largest]) then
swap i largest
downHeap largest

let rec upHeap i =
let parent = i/2
if (i>1) && (less aa.[parent] aa.[i]) then
swap i parent
upHeap parent

// Clear the heap and the array.
member this.Clear () =
Array.mapi
(fun i a -> aa.[i]<-Unchecked.defaultof<'a>)
aa |> ignore
cursor <- 0

// Returns the number of items on the heap.
member this.Count
with get () = cursor

// Drop the top item.
member this.Drop () =
if cursor<1 then failwith "Underflow"
swap 1 cursor
cursor <- cursor-1
downHeap 1

// Insert an item.
member this.Insert a =
incCursor()
aa.[cursor] <- a
upHeap cursor

// Return the top item.
member this.Top
with get () = aa.[1]

// Drop the top item and return it.
member this.Extract () =
let top = this.Top
this.Drop()
top


// Tests.

let h = BinaryHeap<int>((>),16,16)

let r = new System.Random()

h.Insert (r.Next 100)
h.Insert (r.Next 100)
h.Insert (r.Next 100)
h.Insert (r.Next 100)

printf "%i " (h.Extract())
printf "%i " (h.Extract())
printf "%i " (h.Extract())
printf "%i " (h.Extract())


System.Console.ReadLine() |> ignore

No comments: