"""
    BNKeyType

Keys can hold value of type T or nothing.
"""
BNKeyType = Union{T, Nothing} where T

"""
    BNode

Binary node.
"""
mutable struct BNode{T}
    key::BNKeyType{T}
    left::BNode{T}
    right::BNode{T}
    BNode{T}() where T = (x = new(); x)
    BNode{T}(k::BNKeyType{T}) where T = (x = new(); x.key = k; x)
    BNode{T}(k::BNKeyType{T}, l::BNode{T}, r::BNode{T}) where T = new(k, l, r)
end

"""
    RMHeap

Randomised meldable heaps type.
"""
mutable struct RMHeap{T}
    root::BNode{T}
    N::Int
    RMHeap{T}() where T = new(BNode{T}(), 0)
end

"""
    add!(rmheap, x)

Add to the heap.
"""
function add!(rmheap::RMHeap{T}, x::T) where T
    rmheap.root = meld(rmheap.root, BNode{T}(x))
    rmheap.N += 1
    return nothing
end

"""
    remove(rmheap)

Remove minimum element from the heap.
"""
function remove!(rmheap::RMHeap{T}) where T
    x = rmheap.root.key
    rmheap.N -= 1
    if !isdefined(rmheap.root, :left) && !isdefined(rmheap.root, :right)
        rmheap.root = BNode{T}()
        return x
    end
    if !isdefined(rmheap.root, :left)
        rmheap.root = rmheap.root.right
        return x
    end
    if !isdefined(rmheap.root, :right)
        rmheap.root = rmheap.root.left
        return x
    end
    rmheap.root = meld(rmheap.root.left, rmheap.root.right)

    return x
end

"""
    meld!(rmheap, other)

Meld two heaps.
"""
function meld!(rmheap::RMHeap{T}, other::RMHeap{T}) where T
    rmheap.root = meld(rmheap.root, other.root)
    other.root = BNode{T}()
    return nothing
end

"""
    meld(node1, node2)

Meld two nodes.
"""
function meld(node1::BNode{T}, node2::BNode{T}) where T
    if node1.key === nothing return node2 end
    if node2.key === nothing return node1 end

    if node1.key > node2.key
        tmp = node1
        node1 = node2
        node2 = tmp
    end

    if rand((0, 1)) == 1
        if !isdefined(node1, :left) node1.left = BNode{T}() end
        node1.left = meld(node1.left, node2)
    else
        if !isdefined(node1, :right) node1.right = BNode{T}() end
        node1.right = meld(node1.right, node2)
    end

    return node1
end

"""
    getmin(rmheap)

Get the minimum element, don't remove.
"""
getmin(rmheap::RMHeap) = rmheap.root.key

"""
    length(rmheap)
    size(rmheap)

Get size of priority queue.
"""
length(rmheap::RMHeap) = rmheap.N
size(rmheap::RMHeap) = length(rmheap)

# iterate
"""
    eltype(type)

Type of elements generated by iteration over a linked list.
"""
eltype(::RMHeap{T}) where T = T

"""
    isempty(rmheap)

Check if priority queue is empty.
"""
isempty(rmheap::RMHeap) = rmheap.N == 0

"""
    MinPQ

Binary heap minimum priority queue.
"""
mutable struct MinPQ{T}
    root::Vector{T}
    N::Int
    MinPQ{T}(n::Int) where T = new(Vector{T}(undef, n), n)
    MinPQ{T}() where T = new(Vector{T}(undef, 0), 0)
end

"""
    add(pq, x)

Add element to the priority queue.
"""
function add!(pq::MinPQ{T}, x::T) where T
    pq.N += 1
    push!(pq.root, x)
    swim!(pq, pq.N)

    return nothing
end

"""
    remove!(pq)

Remove and get the smallst element from the priority queue.
"""
function remove!(pq::MinPQ)
    if pq.N == 0 return nothing end

    min = pq.root[1]
    pq.root[1] = pq.root[pq.N]
    pq.root[pq.N] = min
    pop!(pq.root)
    pq.N -= 1
    sink!(pq, 1)

    return min
end

"""
    swim!(pq)

Increase an elements priority in the priority queue.
"""
function swim!(pq::MinPQ, k::Int)
    while k > 1 && greater(pq, k ÷ 2, k)
        tmp = pq.root[k ÷ 2]
        pq.root[k ÷ 2] = pq.root[k]
        pq.root[k] = tmp
        k = k ÷ 2  
    end

    return nothing
end

"""
    sink!(pq, k)

Lower a node in the priority queue.
"""
function sink!(pq::MinPQ, k::Int)
    while 2k <= pq.N
        j = 2k
        if j < pq.N && greater(pq, j, j + 1) j += 1 end
        if !greater(pq, k, j) break end
        tmp = pq.root[k]
        pq.root[k] = pq.root[j]
        pq.root[j] = tmp
        k = j
    end

    return nothing
end

"""
    isempty(pq)

Check if priority queue is empty.
"""
isempty(pq::MinPQ) = pq.N == 0

"""
    getmin(pq)

Get the smallest element from priority queue, don't remove.
"""
getmin(pq::MinPQ) = pq.root[1]

"""
    greater(pq, i, j)

Check if element i is larger than element j in priority queue.
"""
greater(pq::MinPQ, i::Int, j::Int) = pq.root[i] > pq.root[j]

"""
    length(pq)
    size(pq)

Get size of priority queue.
"""
length(pq::MinPQ) = pq.N
size(pq::MinPQ) = length(pq)

"""
    isheap(heap)
    isheap(node)
    isheap(pq)

Check that heap invariant holds.
"""
isheap(heap::RMHeap) = isheap(heap.root)
function isheap(node::BNode)
    if isdefined(node, :left)
        if node.key > node.left.key
            return false
        end
        isheap(node.left)
    end
    if isdefined(node, :right)
        if node.key > node.right.key
            return false
        end
        isheap(node.right)
    end

    return true
end

function isheap(pq::MinPQ)
    if isempty(pq) return true end
    data = pq.root

    i = 1
    while 2i <= pq.N
        if !(data[i] <= data[2i]) return false end
        if 2i + 1 > pq.N break end  
        if !(data[i] <= data[2i + 1]) return false end
        i += 1
    end

    return true
end