Function to check if a value is contained in a MutableBinaryHeap

General Usage
1

Hello everyone.

Yesterday I posted this question

I found a solution that I would like to share, given an input heap (minhp) and a value that I want to look for (node):

function searchhp(minhp,node)
    #this function tests if a node is contained in a heap
    b=extract_all!(minhp)
    c=first.(b)
    d=node in b
    minhp=MutableBinaryHeap(Base.By(last),b)
    return d,minhp
end

Basically, what this is doing is turning the heap into a tuple, searching the value, and then transforming back the tuple into the heap.

I worries me that going back and forth from tuple to heap may be computationally expensive for big heaps, but is the only solution that I could find.

If anyone has any idea on a better way to test if a value is contained in a MutableBinaryHeap, I would really appreciate it.

Regards

2

First, you could have posted in that same thread, instead of creating a new one.

Second, if you often need to check if a heap contain a value, then a heap is probably not the most adequate data structure, I recommend using another one, like an OrderedDict or my own TrackingHeap (see the fourth point below).

Third, yes, this is horrendous for performance, I really do not recommend doing it. At this point you would be better with a simple unordered Vector and searching it with findmin and findfirst. You should also not be creating a b just to use in, use findfirst(x -> first(x) == node, b) !== nothing instead.

Fourth, if you need to use a heap, I recommend my own competing solution TrackingHeaps.jl. It conforms to the Dict interface, and using it you could just do findfirst(x -> first(x) == node, values(minhp)) !== nothing to do a linear search without any performance penalty (values does not copy, so you are just directly accessing the Vector with the values).

3

Hi Henrique, thank you for taking the time to reply.
Your feedback is highly appreciated. I will definitely try TrackingHeaps.jl

Thanks.

1 Like