# Indexing Binary Heaps

Binary heaps can be stored in a flat array:

```
heap: [1, 2,3, 4,5,6,7, 8,9,10,11,12,13,14,15, ...]
parent: 1 1 2 2 3 3 4 4 5 5 6 6 7 7
```

The root is `1`

, which has children `2,3`

. The `2`

has children `4,5`

, etc.
The parent of each element is written below it.

Our three questions of today are:

- How do we compute the index of the parent of node i?
- How do we compute the index of the left child of node i?
- How do we compute the index of the right child of node i?

Wikipedia gives us the answer, but Wikipedia’s derivation of the formulas is fairly complex and requires a bit of mathematical calculation.

**We will derive these formulas without any calculation. You will immediately understand why the formulas work:**

Surprisingly, 1-based indexing is better in this particular situation. Let’s write our heap indices in binary:

```
heap: [1, 10,11, 100,101,110,111, 1000,1001,1010,1011,1100,1101,1110,1111, ...]
parent: 1 1 10 10 11 11 100 100 101 101 110 110 111 111
```

As you can see, each level consists of numbers `10..00`

through `111..11`

.
Finding the parent of an index simply amounts to removing the last digit!
Finding the left child amounts to adding a 0 at the end, and finding the right child amounts to adding a 1 at the end:

```
parent(i) = i >> 1
left(i) = (i << 1) + 0
right(i) = (i << 1) + 1
```

That’s it! When you turn these into 0-based indices, you indeed get the formulas on Wikipedia, but we got them without any calculation :)