Efficiently Getting Second Element of std::*_heap

Question

After rigorous profiling, I have determined that the most expensive operations in my program are heap operations on a fairly small (usually <5, almost always <20) heap.

One such operation is getting the second element (i.e., the one below the head). The current way I get the second element is fairly naïve:

1. Remove the first element
2. Check the head
3. Push the element back

I'm assuming that heaps created with e.g. std::make_heap do not need to be laid out in any particular way (e.g. the left side comes first). This complicates just taking e.g. the second element of the backing store.

A linear search would be pretty fast in this case, but again, I'm trying to squeeze all the performance out of this as possible.

So, question: Is there an implementation-independent method to query the second element of heaps created using std::*_heap that is more efficient than just removing the first element and seeing what's on top?

Answer 1

For better or worse, make_heap isn't defined quite strictly enough to guarantee exactly what sort of heap it creates.

You may want to implement your own binary heap, which will let you implement this very quickly (constant complexity). On a normal binary heap (which is what make_heap probably creates, but there's no guarantee of it) the child nodes of some node N are always at 2N and 2N+1. There's no guarantee which of those two will be the next item in the heap, so you have to check both.

The same basic idea will apply to other kinds of heaps, but the exact location may vary (and thus the advice that you may want to implement your own, much as I hate to give that particular advice).