Should PriorityQueue actually be a dictionary?

[devmotion]

Currently, PriorityQueue is implemented as an AbstractDict by wrapping a Dict instance. Apparently, this design mixes two different data structures, and since this leads to performance issues (e.g., #596) I'm wondering if this should be changed.

Instead, alternatively PriorityQueue could be implemented as a wrapper of a heap structure for pairs (by default a BinaryHeap but adjustable by the user) that provides a consistent interface for accessing the top element, its key and its value, removing the top element, and inserting elements, without additionally serving as a dictionary (similar to, e.g., the std::priority_queue in C++). If users need a dictionary structure as well, they can create one independently of the PriorityQueue. This separation would also make it easier to use alternative dictionary types such as SwissDict or RobinDict.

[gdalle]

Just stumbled upon this issue, and it speaks to me since I implemented my own VectorPriorityQueue to improve performance. Even without heap structure, just with basic pushing and popping, I think I already saw improvement over the dict approach.
The code is very simple, would it make sense to add it as an alternative for smallish queues? It is not yet thoroughly tested but I can look into it if it seems interesting to the DataStructures folks

struct VectorPriorityQueue{K,V}
    keys::Vector{K}
    values::Vector{V}
end

VectorPriorityQueue{K,V}() where {K,V} = VectorPriorityQueue{K,V}(K[], V[])

function enqueue!(pq::VectorPriorityQueue{K,V}, k::K, v::V) where {K,V}
    left = searchsortedfirst(pq.values, v)
    insert!(pq.keys, left, k)
    insert!(pq.values, left, v)
end

function Base.deleteat!(pq::VectorPriorityQueue, i::Integer)
    deleteat!(pq.keys, i)
    deleteat!(pq.values, i)
end

function dequeue!(pq::VectorPriorityQueue)
    k = popfirst!(pq.keys)
    popfirst!(pq.values)
    return k
end

Base.length(pq::VectorPriorityQueue) = length(pq.keys)
Base.keys(pq::VectorPriorityQueue) = pq.keys
Base.values(pq::VectorPriorityQueue) = pq.values
Base.isempty(pq::VectorPriorityQueue) = isempty(pq.keys)
Base.pairs(pq::VectorPriorityQueue) = (k => v for (k, v) in zip(pq.keys, pq.values))

[itsdfish]

@gdalle, thanks for sharing. This is useful for me. Do you happen to know how to extend Base.iterate in your proposal? I've been struggling with that.

Edit:

I suppose it could be a simple as

 function Base.iterate(pq::VectorPriorityQueue, c=1)
    if c ≥ length(pq)
        return nothing 
    end
    return pq.keys[c] => pq.values[c], c + 1
end