Mutable pairing heap implementation

pairingheaps_mutable.jl

#
#  Mutable Pairing heap. This version only allocates new nodes when you
#  create a heap or add elements to it, so number of allocations == number of nodes. Has O(1) merges.
#  Performance is not yet optimized and is much slower than an immutable persistent version I wrote,
#  Performance difference may possibly be due to the generational GC making allocation cheaper & more cache friendly,
#  and mutating pointers from old to new nodes more expensive than in C or Rust.
#

struct EmptyHeap{T} end 
mutable struct PairingTree{T}
    top::T
    length::Int
    subheaps::Union{PairingTree{T},Nothing}  # Heap property: all nodes reachable from this field have a larger top element
    tail::Union{PairingTree{T},Nothing} # Intrusive linked list.
end
const PairingHeap{T} = Union{EmptyHeap{T},PairingTree{T}}

Base.show(io::IO,pt::PairingTree{T}) where {T} = show(io,"PairingTree{$(T)}($(pt.top),$(pt.length),$(isnothing(pt.subheaps) ? "empty" : "..." ))") 

singleton_heap(x::T) where {T} = PairingTree{T}(x,1,nothing,nothing)
heap_from_iter(x) = mapreduce(singleton_heap,merge_heaps,x;init=EmptyHeap{eltype(x)}())

peek_min(heap::PairingTree) = heap.top

merge_heaps(x::EmptyHeap,::EmptyHeap) = x
merge_heaps(x,::EmptyHeap) = x
merge_heaps(::EmptyHeap,x) = x
function merge_heaps(x,y) # Inputs are destroyed/invalidated.
    if x.top < y.top
        x.length += y.length
        x.tail = nothing
        x.subheaps = cons_as_intrusive_list!(y,x.subheaps)
        x
    else
        y.length += x.length
        y.tail = nothing
        y.subheaps = cons_as_intrusive_list!(x,y.subheaps)
        y
    end
end
function cons_as_intrusive_list!(a::PairingTree,::Nothing)
    a.tail = nothing
    a
end
function cons_as_intrusive_list!(a::PairingTree{T},b::PairingTree{T}) where {T} 
    a.length += b.length
    a.tail = b
    a
end

insert(heap,x) = merge_heaps(singleton_heap(x),heap)

struct PairMerger{T}
    list::Union{PairingTree{T},Nothing}
end
Base.eltype(::Type{PairMerger{T}}) where {T} = PairingTree{T}
Base.IteratorEltype(::Type{PairMerger{T}}) where {T} = Base.HasEltype()
Base.iterate(p::PairMerger) = iterate(p,p.list)
Base.iterate(::PairMerger,::Nothing) = nothing
function Base.iterate(::PairMerger,list::PairingTree)
    t = list.tail
    if isnothing(t) return list,nothing end
    tt = t.tail
    return merge_heaps(list,t) , tt
end

# Returns a new heap with the top element removed, but does not invalidate the old one (old heap points to the new heap).
function delete_min(heap::PairingTree{T}) where {T}
    if isnothing(heap.subheaps) 
        return EmptyHeap{T}()
    end
    heap.subheaps = foldl(merge_heaps,PairMerger{T}(heap.subheaps))
end
pop_min(heap::PairingTree) = (peek_min(heap), delete_min(heap))

Base.length(x::EmptyHeap) = 0
Base.length(x::PairingTree) = x.length

Base.eltype(::Type{<:PairingHeap{T}}) where {T} = T 
Base.IteratorEltype(::Type{<:PairingHeap{T}}) where {T} = Base.HasEltype()
Base.IteratorSize(::Type{<:PairingHeap{T}}) where {T} = Base.HasLength()

Base.iterate(::EmptyHeap,state...) = nothing
Base.iterate(::PairingTree,::EmptyHeap) = nothing
Base.iterate(heap::PairingTree) = pop_min(heap)  # Iterating through a heap sorts it.
Base.iterate(heap::PairingTree,newheap) = pop_min(newheap) # Subsequent iterations become O(N) instead of O(Nlog(N)).