Question

Binary Heap with root index of 1

(a) If a node is at index k , what is its parent’s index?

b) If a node is at index k , what is its left child index?

c) If a node is at index k , what is its right child’s index?

d) What is the largest index of a node has at least a child in a heap with n nodes?

Answer 1

Binary Heap with root index of 1

(a) If a node is at index k , what is its parent’s index?

its parent is located at k/2 index

b) If a node is at index k , what is its left child index?

Answer: its left child is located at 2*k index

c) If a node is at index k , what is its right child’s index?

Answer: its right child is located at 2*k+1. index

d) What is the largest index of a node has at least a child in a heap with n nodes?

Let there be n nodes after node i in layer L, Using this throughout yields left= 2i and right= 2i + 1 for heaps with their root at 1.

such that

last(l)=(2^(L+1))-1

Hencethe largest index of a node has at least a child in a heap with n nodes is (2^(L+1))-1