Question

Assume that a max-heap contains one key equal to 1 and n - 1 keys equal to 2.

In what type of a node is 1 located (in an internal node, in a leaf?). Why?

What is the minimum index i such that A[i] might contain 1?

Answer 1

Given that a max-heap contains one key equal to 1 and n-1 keys equal to 2.

now, The 1 is located in leaf node, because if 1 is located in internal node then it should have a children with 2 which is impossible in max-heap.

So the 1 should be located in leaf node.

Assume the height of tree is h. then the minimu index i such that a[i] might contain 1 is 2^h -1.

Now assume n = 2^k and k = logn base 2. So now the height of the tree will be k-1. So the index will be 2^(k-1) - 1.

So the minimum index will be 2^(k-1) -1 , if n = 2^k