'BinaryMaxHeap' of tuples ordered on second element?

General Usage
1

I have some Float64 data:

julia> data = rand(10)
10-element Vector{Float64}:
 0.7812532624261221
 0.21171331164805607
 0.17972757757421154
 0.18741269983325282
 0.42157861540422026
 0.7922059340808225
 0.258799529427459
 0.5883959190694283
 0.13260864460551547
 0.47544080823605883

I can put this data into a BinaryMaxHeap as follows:

julia> using DataStructures

julia> binmaxheap = BinaryMaxHeap(data)
BinaryMaxHeap{Float64}(Base.Order.ReverseOrdering{Base.Order.ForwardOrdering}(Base.Order.ForwardOrdering()), [0.7922059340808225, 0.5883959190694283, 0.7812532624261221, 0.21171331164805607, 0.47544080823605883, 0.17972757757421154, 0.258799529427459, 0.18741269983325282, 0.13260864460551547, 0.42157861540422026])

julia> first(binmaxheap)
0.7922059340808225

Now suppose I want to preserve the indices in data in my heap. According to the DataStructures.jl docs I can create a generic BinaryHeap that does this as follows:

julia> heapwithindex = BinaryHeap(Base.By(last), collect(enumerate(data)))
BinaryHeap{Tuple{Int64, Float64}, Base.Order.By{typeof(last), Base.Order.ForwardOrdering}}(Base.Order.By{typeof(last), Base.Order.ForwardOrdering}(last, Base.Order.ForwardOrdering()), [(9, 0.13260864460551547), (4, 0.18741269983325282), (3, 0.17972757757421154), (2, 0.21171331164805607), (5, 0.42157861540422026), (6, 0.7922059340808225), (7, 0.258799529427459), (8, 0.5883959190694283), (1, 0.7812532624261221), (10, 0.47544080823605883)])

julia> first(heapwithindex)
(9, 0.13260864460551547)

julia> ans[1] == argmin(data)
true

However, this is a min heap, not a max heap as required.

How can I modify the call to BinaryHeap() to create a max heap? How about a max-min heap?

  • Calling BinaryMaxHeap(Base.By(last), data) produces an error.

Furthermore, how can I create an empty (min or max) heap ordered on the second entry of the tuple?

  • Calling BinaryHeap(Base.By(last)) without the second argument produces an error (as it should, because there is no input data to show that the entries will be Tuple{Int64,Float64}}s).

  • Calling BinaryMinHeap{Tuple{Int64, Float64}}(Base.By(last)) also errors.

  • My current workaround for an empty such min heap is h = BinaryHeap(Base.By(last), [(1, 0.0)]); extract_all!(h).

1 Like