GATE CSE 2001 | Question: 1.15

Question

Consider any array representation of an $n$ element binary heap where the elements are stored from index $1$ to index $n$ of the array. For the element stored at index $i$ of the array $(i \leq n)$, the index of the parent is

• A. $i-1$
• B. $\lfloor \frac{i}{2} \rfloor$
• C. $\lceil \frac{i}{2} \rceil$
• D. $\frac{(i+1)}{2}$

Comments

       1
     /   \
   2     3
 
a. (i-1)  ,  3-1 = 2  ❌
c. taking ceil (2/2) = 1,   ceil(3/2) = 2  ❌
b. taking floor(2/2) = 1,  floor(3/2) = 1  ✔
d. (i+1)/2 ,  for  i = (3+1)/2 = 2  ❌

---

all binary heap are cbt
 

Answer 1

for node at index $i$

left $child(L)$ at $2$i

right $child(R)$ at $2i+1$

for node at index $i$

parent will be at floor $i/2$

Correct Answer: $B$

Comments

left child: 2i+1

right child: 2i+2

---

simple intuition to check whether floor or ceil value – it depends on the type of indexing.

indexing from 1 gives floor i/2 whereas indexing from 0 gives ceil i/2, to ensure this just draw a binary tree of whatever no of nodes and verify!

---

If we start the index for "0" then the parent index will be : ceil(i/2) - 1

Answer 2

ans b)

Comments

ans is B.

just draw the heap and number the elements.

---

Strange, why is this chosen as wrong answer despite b being the correct opiton

---

maybe not explained thats why