Reasonably fast pairing heap implementation

pairingheaps.jl

struct EmptyHeap{T} end 
struct PairingTree{T}
    top::T
    length::Int
    subheaps::Union{PairingTree{T},Nothing}
    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)
    l = x.length + y.length
    if x.top < y.top
        PairingTree(x.top,l,cons_as_intrusive_list(y,x.subheaps),nothing)
    else
        PairingTree(y.top,l,cons_as_intrusive_list(x,y.subheaps),nothing)
    end
end
cons_as_intrusive_list(a::PairingTree,::Nothing) = PairingTree(a.top,a.length,a.subheaps,nothing)
cons_as_intrusive_list(a::PairingTree{T},b::PairingTree{T}) where {T} = PairingTree(a.top,a.length+b.length,a.subheaps,b)

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
    return merge_heaps(list,t) , t.tail
end

delete_min(heap::PairingTree{T}) where {T} = foldl(merge_heaps,PairMerger{T}(heap.subheaps);init=EmptyHeap{T}())
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(heap::EmptyHeap,state...) = nothing
Base.iterate(heap::PairingTree) = pop_min(heap)
Base.iterate(heap::PairingTree,newheap) = pop_min(newheap)