## 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``