Storing a Heap in an Array

ArrayHeap stores a binary heap in an array, in level order, with the root at index 0.

Solution

A heap is always a complete tree, and a complete tree has exactly one shape for each size. Numbering its nodes in level order fills indices 0 through $n - 1$ with nothing skipped. A tree that is not complete has missing nodes in the middle of the numbering, and their slots would be empty.

Exercise

Write the array that stores this min-heap.

                       ╭────╮
                       │ 15 │
                       ╰──┬─╯
             ┌────────────┴────────────┐
          ╭──┴─╮                    ╭──┴─╮
          │ 35 │                    │ 25 │
          ╰──┬─╯                    ╰──┬─╯
       ┌─────┴─────┐              ┌────┴────┐
    ╭──┴─╮      ╭──┴─╮         ╭──┴─╮    ╭──┴─╮
    │ 45 │      │ 40 │         │ 30 │    │ 55 │
    ╰──┬─╯      ╰────╯         ╰────╯    ╰────╯
   ┌───┘
╭──┴─╮
│ 60 │
╰────╯

Solution

  0    1    2    3    4    5    6    7
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 15 │ 35 │ 25 │ 45 │ 40 │ 30 │ 55 │ 60 │
└────┴────┴────┴────┴────┴────┴────┴────┘

Solution

Left child at $2 i + 1$ , right child at $2 i + 2$ , parent at $(i - 1) /2$ with integer division.

Index 3 holds 45. Its parent is at $(3 - 1) /2 = 1$ , which holds 35. Its left child is at index 7, which holds 60. Its right child would be at index 8, past the last filled index, so it has no right child.