(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:
Post a Comment