PriorityQueue allocations in a simple loop

For this simple benchmark I see unexpected allocations.

using DataStructures, BenchmarkTools

function pq_bench_delete()
  ppq = PriorityQueue{Int, Int}()
  for i in 1:1000000
    enqueue!(ppq, i, i)
    delete!(ppq, i)
  end
end

julia> @benchmark pq_bench_delete()
BenchmarkTools.Trial: 
memory estimate:  41.96 MiB
allocs estimate:  250006
  -------------- 
  minimum time:     207.705 ms (0.60% GC)  
  median time:      210.845 ms (0.56% GC)
  mean time:        211.719 ms (0.54% GC)
  maximum time:     222.605 ms (0.00% GC)
  -------------- 
  samples:          24 
  evals/sample:     1

I am not sure what is the root cause of these allocations. Two things I've noticed though are:

1. If delete!(ppq, i) is replaced with empty!(ppq) allocations go away, so the problem is probably not due to enqueue!.
2. After I've changed PriorityQueue.index underlying storage from Dict to RobinDict allocations disappeared. (this fix also works, when underlying keys are not Int - I've tried Float64)

julia> @benchmark pq_bench_delete()
  BenchmarkTools.Trial:  
  memory estimate:  800 bytes 
  allocs estimate:  7
  --------------
  minimum time:     186.678 ms (0.00% GC)
  median time:      197.709 ms (0.00% GC)
  mean time:        195.674 ms (0.00% GC)
  maximum time:     202.948 ms (0.00% GC)
  --------------
  samples:          26
  evals/sample:     1

Speed up is not dramatic and there might be other places, where performance drops due to the use of RobinDict, however, would it be an ok idea to add an option of choosing the container for indices? Or can somebody see what is the problem with current implementation?

Thanks!

Start with the PriorityQueue.index storage and the delete!(ppq, i) path, then reproduce the supplied @benchmark pq_bench_delete() case. Compare Dict and RobinDict behavior and trace where allocations arise; done means identifying the cause and determining whether the implementation or an index-container option should change.