Giacomo Drago wrote:
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 ]
Well that doesn't look like "each level is kept sorted" to me, but thanks for the further explanation of what you're actually doing. It is possible that this is a novel structure. I'm not convinced that it is useful. If you want a reasonably compact representation, i.e. without the overhead of per-item pointers, but need fast insertion and lookup (both in terms of computational complexity and absolute speed), then an in-memory B tree is hard to beat. Regards, Phil.