DataStructures.jl
DataStructures.jl copied to clipboard
Add (`keys()` and) `values()` interfaces for (mutable) binary heaps
Occasionally we need to iterate through all of the elements of a heap but don't care about the order. In this situation, using extract_all!(h)
is wasteful because it costs O(n log n)
to return the elements in sorted order (and also mutates the heap). In DataStructures.jl, accessing h.valtree
directly is more efficient at O(n)
; however, this field is not documented.
This PR adds the more Julian interface Base.values(h) = h.valtree
for BinaryHeap
s and BinaryMinMaxHeaps
.
julia> using DataStructures
julia> h = BinaryMaxHeap(rand(5))
BinaryMaxHeap{Float64}(Base.Order.ReverseOrdering{Base.Order.ForwardOrdering}(Base.Order.ForwardOrdering()), [0.9829465592187847, 0.8428991971652844, 0.7707265509429536, 0.47963097130235544, 0.17748799914754054])
julia> values(h)
5-element Vector{Float64}:
0.9829465592187847
0.8428991971652844
0.7707265509429536
0.47963097130235544
0.17748799914754054
julia> h = BinaryMinMaxHeap(rand(5))
BinaryMinMaxHeap{Float64}([0.025268923626285966, 0.8282336623952297, 0.976681573216973, 0.14183939323945371, 0.6669349808193425])
julia> values(h)
5-element Vector{Float64}:
0.025268923626285966
0.8282336623952297
0.976681573216973
0.14183939323945371
0.6669349808193425
For MutableBinaryHeaps
, it also adds Base.keys(h) = h.node_map
and Base.values(h)
which returns an iterator over the values.
julia> h = MutableBinaryMaxHeap(rand(5))
MutableBinaryHeap(0.9872660968754716, 0.8597302788167083, 0.7713500693829297, 0.600486099809733, 0.7149676391647972)
julia> keys(h)
5-element Vector{Int64}:
4
3
2
5
1
julia> values(h)
Base.Generator{Vector{Int64}, DataStructures.var"#3#4"{MutableBinaryMaxHeap{Float64}}}(DataStructures.var"#3#4"{MutableBinaryMaxHeap{Float64}}(MutableBinaryHeap(0.9872660968754716, 0.8597302788167083, 0.7713500693829297, 0.600486099809733, 0.7149676391647972)), [4, 3, 2, 5, 1])
julia> Dict(zip(keys(h), values(h)))
Dict{Int64, Any} with 5 entries:
5 => 0.714968
4 => 0.600486
2 => 0.85973
3 => 0.77135
1 => 0.987266
I have included unit tests and documentation.
(This is my first time submitting a pull request on GitHub. I have made every effort to follow the contrib guide, but I apologize in advance if I have done anything wrong. The first commit in my fork mentions the names drain()
and drain!()
, which are the names used for this operation in Rust, but I renamed them in a subsequent commit to match similar Julia built-ins.)
I would really need this feature too! Any chance this gets merged? The implementation seems good to me