Efficiently getting second element of std :: * _ heap
After careful 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 to obtain a second element (i.e., one under the head). The current way to get the second element is pretty naive:
- Remove first item
- Check the head
- Click the item back
I am assuming that heaps created with, for example, std :: make_heap do not need to be laid out in any particular way (for example, on the left side). This complicates the process of receiving, for example, the second item of the backing store.
In this case, linear search will be pretty fast, but again, I try to squeeze all the possibilities out of this as much as possible.
So the question is: Is there an implementation-independent method for requesting the second heap item created with std :: * _ heap that is more efficient than just removing the first item and seeing what's on top?
source to share
For better or worse, make_heap
it is not defined strictly enough to guarantee exactly what kind of heap it creates.
You might want to implement your own binary heap, which will allow you to implement this very quickly (constant complexity). On a normal binary heap (which it probably creates make_heap
, but there is no guarantee), the child nodes of some node N are always at 2N and 2N + 1. There is no guarantee which of these two will be the next item in the heap, so you should check both ...
The same basic idea will apply to other types of heaps, but the exact location can vary (and hence advice you can implement yourself, just as I hate to give this particular advice).
source to share