--- /dev/null
+module Heap
+
+open System.Collections.Generic
+
+let inline private parent (i: int) : int = (i - 1) / 2
+let inline private left (i: int) : int = 2 * (i + 1) - 1
+let inline private right (i: int) : int = 2 * (i + 1)
+
+type private Node<'k, 'v> = { key: 'k; value : 'v } with
+ override this.ToString () = sprintf "%A -> %A" this.key this.value
+
+type Heap<'k, 'v when 'k : comparison> () =
+ let a = List<Node<'k, 'v>>()
+
+ let rec heapUp (i: int) =
+ let l, r = left i, right i
+ let mutable max = if l < a.Count && a.[l].key > a.[i].key then l else i
+ if r < a.Count && a.[r].key > a.[max].key
+ then
+ max <- r
+ if max <> i
+ then
+ let tmp = a.[i]
+ a.[i] <- a.[max]
+ a.[max] <- tmp
+ heapUp max
+
+ member this.Next () : 'k * 'v =
+ let { key = key; value = value} = a.[0]
+ a.RemoveAt(0)
+ key, value
+
+ member this.Add (key: 'k) (value: 'v) =
+ a.Insert(0, { key = key; value = value})
+ heapUp 0
+
+ member this.IsEmpty = a.Count = 0
+ member this.Max : 'k = a.[0].key
+ member this.Clear () = a.Clear()
+
+