Consider a binary heap, with n elements. Only the shape is important; the sorting property doesn't matter here. I'm trying to figure out the offset of the root element in an in-order traversal. Thus, if the heap had size 10, the tree would look like:

       O
     /   \                     .
    O     O
   / \   / \                   .
  O   O O   O
 /\  /
O O O

Moreover, the tree (with nodes replaced by their offsets in an in-order traversal) would look like:

       6
     /   \                    .
    3     8
   / \   / \                  .
  1   5 7   9
 /\  /
0 2 4

...and the root element would have offset 6. How can I figure this out? I have a horrible-looking O(1) algorithm which I haven't tested and which requires the next-power-of-two operation, and of course a naive O(n) implementation. Does anyone know of a simpler way to figure this out?

Quote: Original post by Sneftel
[...] I have a horrible-looking O(1) algorithm which I haven't tested and which requires the next-power-of-two operation, and of course a naive O(n) implementation. Does anyone know of a simpler way to figure this out?

I don't follow. It seems what you're asking for is the number of nodes in the left subtree of the root (the root offset being that number). An O(1) algorithm means that you cannot be traversing the tree at all to determine the size of the root's left subtree. Instead, it implies that you have a priori (stored) data that tells you the in-order index number of the root. But if you had that, you wouldn't be posting the question here (because then the answer is apparent)!

So, are you sure you're releaving all relevant information about this problem (and not omitting e.g. a particular storage approach)? Unless I'm grossly misreading you, as formulated, the only solution I see is isomorphic to counting the nodes in that left subtree, which, of course, is O(n).

Edit: Ahh... it wasn't clear to me that 'n' was actually known! Nevermind then.


[Edited by - Christer Ericson on January 13, 2007 3:00:51 AM]

There are floor(log(n+1)) complete rows in the tree. Let's call this r.

In these complete rows there are 2^r - 1 nodes. There are (2^r - 2)/2 nodes left of the root in the complete rows.

The next row can have up to 2^r elements in it. It actually has n - (2^r - 1) elements. Of these, only the first 2^(r-1) are on the left side of the tree. The number of nodes in the incomplete row and on the left half of the tree is therefore min(2^(r-1), n - (2^r - 1)).

The offset of the root is then:

r = floor(log(n+1))
(2^r - 2)/2 + min(2^(r-1), n - (2^r - 1))

or

2^(r-1) - 1 + min(2^(r-1), n - (2^r - 1))

I'm guessing your O(1) solution looks a lot like this.

I was thinking of a similar logic, where you first find the next lowest power-of-two. This flushes out the bottom level to a single element. You then adjust the result to take into account any elements that were flushed from the left subtree. Something like:

x = next_lowest_power_of_2(n);x += min(x/2 - 1, n - x);

Same idea as Vorpy though, just a few off-by-one differences.