Pairing heap implementation

pairingheaps.jl

##
## This seems to consistently crash Julia
##

using FunctionalCollections
using ResumableFunctions

struct EmptyHeap end 
struct PairingTree{T}
    top::T
    length::Int
    subheaps::PersistentVector{PairingTree{T}}
end

const PairingHeap{T} = Union{EmptyHeap,PairingTree{T}}

singleton_heap(x::T) where {T} = PairingTree{T}(x,1,PersistentVector{PairingTree{T}}())
heap_from_iter(x) = foldl(insert,x;init=EmptyHeap())

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,push(x.subheaps,y))
    else
        PairingTree(y.top,l,push(y.subheaps,x))
    end
end

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

delete_min(heap::PairingTree) = foldl(merge_heaps,merged_pairs(heap.subheaps);init=EmptyHeap())

@resumable function merged_pairs(list::PersistentVector{PairingTree{T}}) :: PairingTree{T} where {T}
    while !isempty(list)
        ret = FunctionalCollections.peek(list) 
        remainder = pop(list)
        if isempty(remainder)
            list = remainder
            @yield ret
        else
            ret = merge_heaps(ret,FunctionalCollections.peek(remainder))
            list = pop(remainder)          
            @yield ret
        end
    end
end

pop_min(heap::PairingTree) = (peek_min(heap), delete_min(heap))

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

Base.eltype(::PairingTree{T}) where {T} = T 
Base.iterate(heap::EmptyHeap,state...) = nothing
Base.iterate(heap::PairingTree) = pop_min(heap)
Base.iterate(heap::PairingTree,newheap::PairingHeap) = iterate(newheap) 


function heapsort(arr)
    heap = heap_from_iter(arr)
    [x for x in heap]
end

using Random
for i in 1:1000
    arr = randperm(100)
    if sort(arr) != heapsort(arr)
        println("Test fail")
    end
end