Thanks for your kind reply, Phil. I will answer your questions the best I can. On 2015-03-19 17:05, Phil Endecott wrote:
That almost sounds like an implicit binary tree, except that I guess you're storing the min item in the parent, not the mid. I.e. to store the values 0 to 6, an implicit binary tree would store:
3 1 5 0 2 4 6
The children of item i are at locations 2i+1 and 2i+2. To iterate the items in order, you do a mid-order traversal.
But a (min-) heap with sorted levels would be more like this:
0 1 4 2 3 5 6
In this case you can do a pre-order traversal to get the items in-order.
A simple pre-order traversal? Does it work? In your example it clearly does, but you can also have [ 0 ] [ 1 4 ] [ 2 5 6 7 ] In that case, how do you 'jump' from 2 up to 4 and then down again to 5? How do you know "who's next" (as it can be someone ten levels above)? I am just confused and talking nonsense?
You say that you think your lookup is O(log^2 N), so maybe I've not correctly understood your design.
P.S. Have you looked at Boost.Heap? I used Boost.Heap with great profit in the past. I didn't use any Boost
I basically make a per-level binary search with some minor optimizations easily understandable by reading the code (but I can elaborate, if I am making some sense so far and you wish me to continue). How can you search in O(log N) in a heap where the elements of each level are sorted (not antagonizing, genuinely just asking for curiosity)? If I convinced you so far, then we can get into how insertion and erasure work. library for this project because the implementation is a throwaway prototype and hacking up a modified heap by the means of a std::vector was, for me, the fastest way to get the job done - for now. In the unlikely case this strange and hardly useful data structure made it into Boost, it would be rewritten and properly Boostified, without any reinvention of the wheel of course, and stress tested to death. Best Giacomo