Find what row a given number exists in within a binary heap tree.

Question

If I have a binary heap tree like so:

            1
     2,             3
 4,     5,      6,      7
8, 9, 10, 11, 12, 13, 14, 15
16 ... 31
32 ... 63
64 ... 127

I would say 5 is in row 3, and 115 is in row 7.

I'm sure the equation is stupid simple like "duh, find the square root." But I'm not seeing it.

So how do I determine which row in the heap a given number is in.

115 is in row 7. I have elipses to describe continuing the pattern. It's between 64 and 127. — Suamere, Jan 06 '16 at 23:32

Asinomás · Accepted Answer · 2016-01-06T23:42:29.703

1

Oh ok, gotcha.

number $n$ is going to be in the following level:

$\lfloor \log_2(n) \rfloor +1$

Here is a c++ function for it:

int findfloor(int x){
    int i,j;
    for(i=0,j=1; 2*j <= x; i++,j*=2){}
    return(i+1);
}

edited Jan 06 '16 at 23:42

answered Jan 06 '16 at 23:32

Asinomás

I like that the integer returns 7 where n is 115. But the full result is 7.8454900509443757. While that works, shouldn't I be scared that numbers waaaaay further down might be incorrect? (Possibly too high?) Or is that just a result of it not being the first number in row 7. – Suamere Jan 06 '16 at 23:35
haha, no. the first number on each level is always going to give you the exact value – Asinomás Jan 06 '16 at 23:36
Right, makes sense. Thank you for the super fast and awesome answer. – Suamere Jan 06 '16 at 23:36
Sure, I added a c++ function that finds the floor, just be careful your number is an int under 2^62 – Asinomás Jan 06 '16 at 23:43

1 Answers1