From: rcs@xmission.com

The tree is recursive, building the lower sections as copies of the upper part. 345 follows the pattern of 012, just adding 3 to each node. 15-29 is a +15 copy of 0-14. The next levels will be 255-509.

Yup.

If we added 1 to each entry, the bit patterns might be enlightening.

Maybe, the math involves multiples of 3, 15, 255, etc.

What's the point? Is this a worst case for heapsort?

No, I'm wondering whether a different arrangement, where locations on a path down the tree tend to be closer together, (better "locality of reference") would let heapsort take better advantage of caching and virtual memory. Here is a graph of some timing tests so far. "Vanilla" is the classic heap, "Clumpy" is the one I've been talking about here, and there are other arrangements I've been trying. http://www.tiac.net/~sw/2009/10/Clumpy_heapsort

From: "N. J. A. Sloane" <njas@research.att.com>

what was the rule that made you write

18 19 20

under 16, rather than as the right-hand daughter of 4 ?

Could you spell out the rules more explicitly?

The rule is that you build clump of 3: one parent node with two daughter nodes clump of 15: one upper clump of 3, + 4 lower clumps of 3 clump of 255: one upper clump of 15, 16 lower clumps of 15 65535 = (1 + 256) * 255 etc. So 18 goes under 16 because my rule says to build clumps of 15 (rather than just clumps of 3) starting at 15. The right-hand daughter of 4 is the next clump of 15. Here is one way to describe the sequence of numbers in a row of the clumpy tree. Say that S( i, r, h ) is row r (starting at 0) of a clump of height >= h, whose root is i. S( i, r, h ) = if r = 0: the sequence [ i ] if r >= h: S( i, r, 2h ) # see below else if r < h/2: S( i, r, h/2 ) else the concatenation of the sequences, for j = 1 to 2^(h/2) of S( i + j * ( 2^(h/2) - 1 ), r - h/2, h/2 ) The second case covers all the rows of an infinite tree, by doubling the height until it's enough. So, the whole sequence is the concatenation of the rows: S( 0, 0, 1 ), S( 0, 1, 1 ), S( 0, 2, 1 ), S( 0, 3, 1 )... --Steve