Question

Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i.

instructions: provide Java-like pseudocode. The implicit position of a node refers to the index it would have if the heap was stored in the array format reviewed in class (first element at index 1).

Answer 1

Algorithm is very simple. Since the parent index of element at index i is index i/2 , hence to find the tree node at implicit position i, covert the number i into binary format.

Now the let index i in binary format be b_kb_k-1....b₁b₀ . So process the binary number b_kb_k-1....b₁b₀  from left to right. Starting from bit b_k to bit b₀ if bit b_i is 0 then we will go to left child and if bit b_i is 1 then go to right child. If we follow like this then at the end while accessing bit b₀ we will reach at element with implicit position i. The reason behind this is that, when we reach at bit b_i while processed elements b_kb_k-1....b_i the corresponding index we reached is b_k*2^(k-i)+ b_k-1 * 2^{(k-i+1)*b_k-1}+....+b_i+1*2 + b_i . Hence each subsequent search will multiply the index by 2 if we go to left child and multiply the index by 2 and add 1 if we go to right child and hence finally we reach at index i.

Below is the method:-

node * find( node *root, index i)

{

1. B = binary(i); //B will be array of 0 and 1 storing number i in binary format.

2. node *result = root; //result will store the final node

3. for i = k to 0 //k is the leftmost index of binary number in B

4........if(B[ i ] == 0)

5..............result = result->left; //Go to left child

6.......else

8..............result = result->right; //Go to right child

9........if result==NULL

10...........Return NULL since index i does not exist

11. Return result //This will be final node which will be at implicit position i

}

Now let us convert it into recursive function in java

node * find(node *root, int i)

{

int k=1;

if(i==1)

return(root); //Since the root element of subtree will have index 1

else if(i==2)

return(root->left); //index of root->left is 2

else if(i==3)

return(root->right); //index of root->right is 3

//This is the condition for going to left subtree

//Since now the index of node i will be

  //This is the condition for going to right subtree

//Since now the index of node i will be

}

Please comment for any clarification.