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()