/// The goal is to have a set of data and be able to get the value associated with the min (or max) key value.
/// </summary>
type Heap<'k, 'v> (kComparer : IComparer<'k>) =
- let a = List<Node<'k, 'v>>()
+ let a = List<Node<'k, 'v>> ()
let rec heapUp (i : int) =
let l, r = left i, right i
// Is the left child greater than the parent?
- let mutable max = if l < a.Count && kComparer.Compare(a.[l].key, a.[i].key) > 0 then l else i
+ let mutable max = if l < a.Count && kComparer.Compare (a.[l].key, a.[i].key) > 0 then l else i
// Is the right child greater than the parent and the left child?
- if r < a.Count && kComparer.Compare(a.[r].key, a.[max].key) > 0 then
+ if r < a.Count && kComparer.Compare (a.[r].key, a.[max].key) > 0 then
max <- r
// If a child is greater than the parent.
let l, r = left i, right i
let leftIntegrity =
if l < a.Count then
- if kComparer.Compare(a.[l].key, a.[i].key) > 0 then false else checkIntegrity l
+ if kComparer.Compare (a.[l].key, a.[i].key) > 0 then false else checkIntegrity l
else
true
let rightIntegrity =
if r < a.Count then
- if kComparer.Compare(a.[r].key, a.[i].key) > 0 then false else checkIntegrity r
+ if kComparer.Compare (a.[r].key, a.[i].key) > 0 then false else checkIntegrity r
else
true
leftIntegrity && rightIntegrity
interface IEnumerable<'k * 'v> with
member this.GetEnumerator () : IEnumerator<'k * 'v> =
- (seq { for e in a -> e.key, e.value }).GetEnumerator()
+ (seq { for e in a -> e.key, e.value }).GetEnumerator ()
interface System.Collections.IEnumerable with
member this.GetEnumerator () : System.Collections.IEnumerator =
- (this :> IEnumerable<'k * 'v>).GetEnumerator() :> System.Collections.IEnumerator
+ (this :> IEnumerable<'k * 'v>).GetEnumerator () :> System.Collections.IEnumerator
member this.Next () : 'k * 'v =
let node = a.[0]
a.[0] <- a.[a.Count - 1]
- a.RemoveAt(a.Count - 1)
+ a.RemoveAt (a.Count - 1)
heapUp 0
node.key, node.value
member this.RemoveNext () =
a.[0] <- a.[a.Count - 1]
- a.RemoveAt(a.Count - 1)
+ a.RemoveAt (a.Count - 1)
heapUp 0
member this.Add (key : 'k) (value : 'v) =
- a.Add(Node(key, value))
+ a.Add (Node (key, value))
let mutable i = a.Count - 1
- while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do
+ while i > 0 && kComparer.Compare (a.[parent i].key, a.[i].key) < 0 do
let tmp = a.[parent i]
a.[parent i] <- a.[i]
a.[i] <- tmp
let max = a.[0]
max.key, max.value
- member this.Clear () = a.Clear()
+ member this.Clear () = a.Clear ()