⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠
Text Elements
5
4
1
10
-3
8
11
2
9
11
5
13
18
20
38
[0,1]
[2,3]
[0,3]
[0,7]
[4,5]
[6,7]
[4,7]
log n
[0,4]
[1,6]
5
4
3
0
6
8
-3
4
9
9
11
5
13
20
18
38
[0,2]
[3,4]
[0,4]
[0,8]
[5,6]
[7,8]
[5,8]
[1,6]
9
[0,1]
5
4
1
10
-3
8
9
5
20
18
38
[0,1]
[0,3]
[0,6]
[4,5]
[4,6]
n = 7
Because, in practice, the memory layout is more like this
9
11
5
13
20
18
38
[0,2]
[3,4]
[0,4]
[0,8]
[5,6]
[7,8]
[5,8]
9
[0,1]
5
4
0
3
6
8
-3
4
9
UNUSED nodes
Some examples where n is not a power of 2:
13 total nodes used
17 total nodes used
n = 9
Why do we need 4*n?
1
2
3
4
5
6
7
8
9
16
n = 9
31
17
11
[2,3]
13
5
4
1
11
4
13
9
5
20
18
38
[0,1]
[0,2]
[0,5]
[3,4]
[3,5]
n = 6
11 total nodes used
5
4
1
11
4
13
9
5
20
18
38
[0,1]
[0,2]
[0,5]
[3,4]
[3,5]
n = 6
11 total nodes used
It’s fine for n=9, but consider n = 6
9
5
20
18
38
[0,1]
[0,2]
[0,5]
[3,4]
[3,5]
n = 6
5
4
11
1
4
13
1
2
3
4
5
6
7
8
15
14
13
12
9