Function to check if a value is contained in a MutableBinaryHeap

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
    d=node in b
    return d,minhp

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.


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

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


1 Like