The Array That Holds a Heap

Perfect cache behaviour. The nodes are contiguous, so walking a path reads neighbouring memory. This is the structure chapter 22's warning does not apply to.

The shape maintains itself. Adding an item means appending to the array, which is exactly adding the next node of a complete tree. Removing the last node means shortening the array. The shape property can never be broken, because an array has no gaps. Only the order property needs repairing, and that is what chapter 84 does.

That last point is the elegant part: half the heap's invariant is enforced by the representation rather than by code.

The two operations, in outline

Both are the same two steps in opposite orders, and chapter 84 implements them.

Insert. Append the new value at the end of the array, which keeps the shape. Then move it up until the order property holds. That is at most the height, O(log n).

Remove the best. Take index 0, which is the answer. Move the last element into index 0, which keeps the shape, and shorten the array. Then move it down until the order property holds. Again O(log n).

In both, the shape is fixed first and cheaply, and then the order is repaired.

The off-by-one that ruins it

The 1-based convention of chapter 58 is common in textbooks:

Mixing them is the standard error and it does not fail loudly: the structure continues to work for small indices and goes wrong deeper in. State the convention and use it everywhere, including in the termination conditions of the loops.

def children_zero(i):
    return 2 * i + 1, 2 * i + 2


def parent_zero(i):
    return (i - 1) // 2


def children_one(i):
    return 2 * i, 2 * i + 1


def parent_one(i):
    return i // 2


n = 20
zero_ok = all(parent_zero(c) == i for i in range(n) for c in children_zero(i))
one_ok = all(parent_one(c) == i for i in range(1, n) for c in children_one(i))
print("0-based: parent(child(i)) == i for every i:", zero_ok)
print("1-based: parent(child(i)) == i for every i:", one_ok)
print()
print("mixing them, 0-based children with 1-based parent:")
for i in (0, 1, 2, 3, 7):
    left, _ = children_zero(i)
    print("   node %2d, left child %2d, 1-based parent of that child says %2d  %s"
          % (i, left, parent_one(left),
             "correct" if parent_one(left) == i else "WRONG"))

0-based: parent(child(i)) == i for every i: True
1-based: parent(child(i)) == i for every i: True

mixing them, 0-based children with 1-based parent:
   node  0, left child  1, 1-based parent of that child says  0  correct
   node  1, left child  3, 1-based parent of that child says  1  correct
   node  2, left child  5, 1-based parent of that child says  2  correct
   node  3, left child  7, 1-based parent of that child says  3  correct
   node  7, left child 15, 1-based parent of that child says  7  correct

Interesting, and worth reading carefully: for a left child the mixed arithmetic happens to agree, because (2i + 1) // 2 equals i. The error only shows on right children, which is precisely why it survives casual testing and then fails on real data.

Quick revision

• A heap is stored as an array read level by level, left to right.
• Root at 0; children of i at 2i + 1 and 2i + 2; parent of i at (i - 1) / 2.
• It works because a complete tree has no gaps, so every index below n holds a node.
• No pointers at all, the parent is free, and the memory is contiguous so the cache works.
• The shape property is enforced by the representation: appending adds the next node of a complete tree

and an array cannot have a gap. Only the order needs repairing.

• Insert: append, then sift up. Remove: take index 0, move the last element there, shorten, then sift

down. Both O(log n).

• Mixing the 0-based and 1-based conventions agrees by accident on left children and fails on right ones.

Test yourself

1. Give the index arithmetic for a heap with the root at 0. Children of i at 2i + 1 and 2i + 2; parent of i at (i - 1) divided by 2 with integer division.

2. Why does this representation work for a heap when chapter 58 showed it wasteful for a general tree? Because a heap is always complete, so there are no gaps and every index from 0 to n - 1 holds a real node. A general tree may be degenerate and would need an exponentially large array.

3. Name three things the array representation buys. No pointers at all; the parent of a node for free from arithmetic; and contiguous memory, so the cache works well.

4. Which of the heap's two properties is enforced by the representation, and how? The shape property. Appending to the array adds exactly the next node of a complete tree, and an array cannot contain a gap, so the shape can never be broken. Only the order property needs repairing.

5. Outline insertion and removal. Insert: append at the end, which keeps the shape, then sift the value up until the order holds. Remove: take index 0 as the answer, move the last element to index 0, shorten the array, then sift it down.

6. Why does mixing the 0-based and 1-based conventions survive casual testing? Because for a left child the mixed arithmetic happens to agree: (2i + 1) divided by 2 is i. The error appears only on right children.