3 open System.Collections.Generic
5 let inline private
parent (i
: int) : int = (i
- 1) / 2
6 let inline private
left (i
: int) : int = 2 * (i
+ 1) - 1
7 let inline private
right (i
: int) : int = 2 * (i
+ 1)
10 type private Node<'k, 'v
> =
13 new (k
, v
) = { key = k
; value = v
}
14 override this.ToString () = sprintf
"%A -> %A" this.key this.value
16 type Heap<'k, 'v
> (kComparer
: IComparer<'k>) =
17 let a = List<Node<'k
, 'v>>()
19 let rec heapUp (i: int) =
20 let l, r = left i, right i
22 // Is the left child greater than the parent?
23 let mutable max = if l < a.Count && kComparer.Compare(a.[l].key, a.[i].key) > 0 then l else i
25 // Is the right child greater than the parent and the left child?
26 if r < a.Count && kComparer.Compare(a.[r].key, a.[max].key) > 0
30 // If a child is greater than the parent.
38 // Check the integrity of the heap, use for debug only.
39 let rec checkIntegrity (i: int) : bool =
40 let l, r = left i, right i
44 if kComparer.Compare(a.[l].key, a.[i].key) > 0
52 if kComparer.Compare(a.[r].key, a.[i].key) > 0
57 leftIntegrity && rightIntegrity
59 interface IEnumerable<'k
* 'v> with
60 member this.GetEnumerator () : IEnumerator<'k
* 'v> =
61 (seq { for e in a -> e.key, e.value }).GetEnumerator()
63 interface System.Collections.IEnumerable with
64 member this.GetEnumerator () : System.Collections.IEnumerator =
65 (this :> IEnumerable<'k
* 'v>).GetEnumerator() :> System.Collections.IEnumerator
67 member this.Next () : 'k
* 'v =
69 a.[0] <- a.[a.Count - 1]
70 a.RemoveAt(a.Count - 1)
74 member this.RemoveNext () =
75 a.[0] <- a.[a.Count - 1]
76 a.RemoveAt(a.Count - 1)
79 member this.Add (key: 'k
) (value: 'v) =
80 a.Add(Node(key, value))
82 let mutable i = a.Count - 1
83 while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do
84 let tmp = a.[parent i]
89 member this.IsEmpty = a.Count = 0
90 member this.Count = a.Count
92 member this.Max : 'k
* 'v =
96 member this.Clear () = a.Clear()