in DS edited by
4,897 views
25 votes
25 votes

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

  1. $i-1$
  2. $\lfloor \frac{i}{2} \rfloor$
  3. $\lceil \frac{i}{2} \rceil$
  4. $\frac{(i+1)}{2}$
in DS edited by
4.9k views

2 Answers

33 votes
33 votes
Best answer
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$
edited by

4 Comments

moved by
Ans is floor(i/2) ..

If index starts with 0 than Ceil(i/2)-1
18
18
@papesh What would be the left child and right child if index starts with 0?
0
0
left child: 2i+1

right child: 2i+2
3
3
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!
0
0
4 votes
4 votes
ans b)

1 comment

ans is B.

just draw the heap and number the elements.
0
0