X-Git-Url: http://git.euphorik.ch/?a=blobdiff_plain;f=Parasitemia%2FParasitemia%2FHeap.fs;fp=Parasitemia%2FParasitemia%2FHeap.fs;h=c2ab69f1cab7dab40aad081e16b017de589cfada;hb=84fdf7404133803fdf0dc867a4da68a144975191;hp=0000000000000000000000000000000000000000;hpb=5ac2dedf8ead5275ac216e0b41829ab39c843800;p=master-thesis.git

diff --git a/Parasitemia/Parasitemia/Heap.fs b/Parasitemia/Parasitemia/Heap.fs
new file mode 100644
index 0000000..c2ab69f
--- /dev/null
+++ b/Parasitemia/Parasitemia/Heap.fs
@@ -0,0 +1,41 @@
+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()
+
+