DataStructures.jl icon indicating copy to clipboard operation
DataStructures.jl copied to clipboard

Add (`keys()` and) `values()` interfaces for (mutable) binary heaps

Open maxkapur opened this issue 2 years ago • 1 comments

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 BinaryHeaps 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.)

maxkapur avatar Mar 28 '22 00:03 maxkapur

I would really need this feature too! Any chance this gets merged? The implementation seems good to me

Tortar avatar Mar 24 '24 15:03 Tortar