82298e2fae46034915a55c2ba5e50f8b5586b611
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)
9 // TODO: measure performance with a struct.
10 type private Node<'k, 'v
> = { mutable key: 'k; value : 'v
} with
11 override this.ToString () = sprintf
"%A -> %A" this.key this.value
13 type Heap<'k, 'v
> (kComparer
: IComparer<'k>) =
14 let a = List<Node<'k
, 'v>>()
16 let rec heapUp (i: int) =
17 let l, r = left i, right i
19 // Is the left child greater than the parent?
20 let mutable max = if l < a.Count && kComparer.Compare(a.[l].key, a.[i].key) > 0 then l else i
22 // Is the right child greater than the parent and the left child?
23 if r < a.Count && kComparer.Compare(a.[r].key, a.[max].key) > 0
27 // If a child is greater than the parent.
35 let rec checkIntegrity (i: int) : bool =
36 let l, r = left i, right i
41 if kComparer.Compare(a.[l].key, a.[i].key) > 0
49 if kComparer.Compare(a.[r].key, a.[i].key) > 0
54 leftIntegrity && rightIntegrity
56 interface IEnumerable<'k
* 'v> with
57 member this.GetEnumerator () : IEnumerator<'k
* 'v> =
58 (seq { for e in a -> e.key, e.value }).GetEnumerator()
60 interface System.Collections.IEnumerable with
61 member this.GetEnumerator () : System.Collections.IEnumerator =
62 (this :> IEnumerable<'k
* 'v>).GetEnumerator() :> System.Collections.IEnumerator
64 member this.Next () : 'k
* 'v =
65 let { key = key; value = value } = a.[0]
66 a.[0] <- a.[a.Count - 1]
67 a.RemoveAt(a.Count - 1)
71 member this.RemoveNext () =
72 a.[0] <- a.[a.Count - 1]
73 a.RemoveAt(a.Count - 1)
76 member this.Add (key: 'k
) (value
: 'v) =
77 a.Add({ key = key; value = value })
79 let mutable i = a.Count - 1
80 while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do
81 let tmp = a.[parent i]
86 member this.IsEmpty = a.Count = 0
87 member this.Count = a.Count
89 member this.Max : 'k
* 'v =
93 member this.Clear () = a.Clear()