SME
Data Structures & Algorithms · Problem type
Heap array indices
Use this for “A heap is stored in an array from index 0. What are the parent and children of the node at index 5?”
This is an example. Type your own values to start a new problem.
p
=
⌊(
i
−
1)
÷
2⌋
cL
=
2
×
i
+
1
cR
=
2
×
i
+
2
d
Level of the node
worked out (not typed)
Formulas
p
=
⌊
i
− 1
2
⌋
2
=
⌊
5 − 1
2
⌋
cL
=
2
×
i
+
1
11 = 2 × 5 + 1
cR
=
2
×
i
+
2
12 = 2 × 5 + 2
d
=
⌊log₂(
i
+
1)⌋
2 = ⌊log₂(5 + 1)⌋
Assumptions
•
The heap fills its array level by level from index 0, the root, with no gaps.
•
Each step is constant time: the indices come from arithmetic, with no pointers stored.
•
The root at index 0 has no parent; a child index past the last item means no child.
Step-by-step
WE KNOW
i = 5
FIND
parent index (p), left child index (cL), right child index (cR), level of the node (d)
Step 1 · Find parent index (p)
Use p = ⌊(i − 1) ÷ 2⌋
Children
2
p
+
1
and
2
p
+
2
both
lead
back
to
p
:
take
1
and
halve,
dropping
any
half.
p
=
⌊
5 − 1
2
⌋
⌊
4
2
⌋
=
2
p
=
2
Step 2 · Find left child index (cL)
Use cL = 2 × i + 1
Level
k
starts
at
index
2ᵏ
−
1,
so
the
children
of
i
sit
at
2
i
+
1
and
2
i
+
2.
cL = 2 × 5 + 1
cL = 10 + 1
cL = 11
Step 3 · Find right child index (cR)
Use cR = 2 × i + 2
The right child is next to the left one.
cR = 2 × 5 + 2
cR = 10 + 2
cR = 12
Step 4 · Find level of the node (d)
Use d = ⌊log₂(i + 1)⌋
Level
d
runs
from
index
2ᵈ
−
1
to
2
d
+ 1
−
2,
so
i
+
1
lies
from
2ᵈ
to
just
under
2
d
+ 1
.
d
=
⌊log₂(5
+
1)⌋
⌊log₂
6⌋
=
2,
since
2
2
=
4
≤
6
<
8
=
2
3
d
=
2
Check
Put the numbers back in. Both sides should match.
2
=
⌊
5 − 1
2
⌋
✓
11 = 2 × 5 + 1 ✓
12 = 2 × 5 + 2 ✓
2 = ⌊log₂(5 + 1)⌋ ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Trees and graphs
Main lesson
Adjacency matrix or list size
Use this for “An undirected graph has 1000 vertices and 5000 edges. How many cells does its adjacency matrix take, and how many entries its adjacency list?”
Preorder traversal of a search tree
Use this for “Insert 50, 30, 70, 20, 40, 60, 80 into an empty binary search tree. In what order does a preorder traversal visit the nodes?”