Complete Binary Trees & the Array Encoding

August 2026 · 18 min read

A heap is the answer to a question arrays and sorted arrays both get wrong. You have a pile of items arriving over time, and you repeatedly need the smallest one right now. An unsorted array gives you O(1) insert but O(n) to find the minimum. A sorted array gives you O(1) minimum but O(n) insert. A balanced BST gives you O(log n) for both, but you pay for pointers, allocations, and cache misses you did not need — because you never asked for the third smallest, or for a range, or for sorted iteration. You only ever asked for the extreme.

The heap is what you get when you take a binary search tree and delete every guarantee you were not using. What remains is so weak that it fits in a flat array with no pointers at all — and that is the entire trick of this data structure.

The Shape Rule: Complete Binary Trees

A heap is not any binary tree. It is a complete binary tree: every level is entirely full except possibly the last, and the last level is filled strictly left to right with no gaps.

This is a rigid constraint, and it is deliberate. It pins down the shape completely: for a given number of nodes n, there is exactly one complete binary tree shape. Nothing is left to choose. Compare that with a BST, where n nodes admit Catalan-many shapes, most of them terrible, which is why balanced BSTs need rotations, colours, and rebalancing logic to stay usable.

Two consequences follow immediately, and they are the reason heaps behave so well:

1. The height is always exactly floor(log2(n)). Not amortised, not with high probability, not after rebalancing — always. A complete tree cannot degenerate, because “fill left to right” leaves no room to degenerate.
2. There is exactly one place a new node can go (the next free slot on the last level) and exactly one node that can be removed without breaking completeness (the last node). Insertion and deletion never have to search for a structural position.

Hold on to that second point. Most of the elegance of heap algorithms comes from it: because the structural decision is forced, the only remaining work is fixing the ordering, and that is a single walk up or down one root-to-leaf path.

The Array Encoding

Here is where completeness pays off. Number the nodes in level order — left to right, top to bottom — starting at 0. Because the tree is complete, level order visits the nodes with no gaps. So the numbering is a perfect bijection onto 0, 1, 2, ..., n-1, which is to say: onto an array.

              0:(3)
             /      \
        1:(8)        2:(5)
       /     \      /
   3:(12)  4:(9)  5:(7)

   array:  [ 3, 8, 5, 12, 9, 7 ]
   index:    0  1  2   3  4  5

The tree edges are now implied by arithmetic. For a node at index i:

Verify it against the diagram: node 1 holds 8; its children should be at 2*1+1 = 3 and 2*1+2 = 4, which hold 12 and 9. Correct. The parent of index 4 is (4-1)/2 = 1 under integer division. Correct. And note that integer division does the right thing for both children: (3-1)/2 = 1 and (4-1)/2 = 1, so the two siblings agree on their parent without a special case.

Why the Encoding Is More Than a Trick

It is tempting to file the array encoding under “cute space optimisation”. It is much more than that.

No allocation. A pointer-based tree calls the allocator once per insert and once per erase. A heap on a std::vector amortises to zero allocations after the buffer grows. In a hot loop — a Dijkstra relaxation, an event-driven simulation — that difference dominates the asymptotics you were staring at.

No pointer overhead. A node in a pointer tree costs the payload plus two or three pointers plus allocator bookkeeping; for an int payload that is easily 4x–8x blowup. The heap costs exactly sizeof(T) per element.

Cache behaviour. This one is subtler and cuts both ways. The top levels of the heap live in the first few array slots, so the root and its immediate descendants are almost always hot in L1 — and those are exactly the nodes every operation touches. Deeper down, a parent at i and its child at 2i+1 are far apart in memory, so a sift-down through the bottom levels does incur real cache misses. The net effect is still strongly favourable, and it is the reason d-ary heaps (Part 13) can beat binary heaps by widening the tree to trade depth for locality.

Trivially serialisable. A heap is its array. You can memcpy it, write it to disk, or send it over a socket with no traversal or fixup. Pointer trees cannot do this.

What a Heap Deliberately Cannot Do

Knowing the non-guarantees prevents a whole class of bugs and bad design decisions:

• Search is O(n). There is no ordering between siblings, so finding an arbitrary value means scanning the whole array. If you need “is x present”, a heap is the wrong structure — or needs an auxiliary index (Part 12).
• It is not sorted. [3, 8, 5, 12, 9, 7] is a perfectly valid heap and is obviously not a sorted array. A sorted array is always a valid min-heap, but the converse fails badly.
• Iteration order is meaningless. Walking the underlying array gives you level order, which corresponds to nothing a user wants. To get sorted output you must pop repeatedly — which is precisely heapsort (Part 6).
• Only one end is cheap. A min-heap gives you the minimum in O(1) and says nothing useful about the maximum, which could be at any leaf. Needing both ends means two heaps (Part 9) or a double-ended structure.

The Skeleton in C++

Everything above, with no ordering logic yet — just the shape and the index arithmetic that the rest of the series builds on:

#include <vector>
#include <cstddef>

template <class T>
class BinaryHeap {
    std::vector<T> a;

    static std::size_t parent(std::size_t i) { return (i - 1) / 2; }
    static std::size_t left  (std::size_t i) { return 2 * i + 1; }
    static std::size_t right (std::size_t i) { return 2 * i + 2; }

public:
    bool        empty() const { return a.empty(); }
    std::size_t size () const { return a.size();  }
    const T&    top  () const { return a.front(); }   // the root, O(1)
};

Note parent is only valid for i > 0: at the root, (0-1)/2 on an unsigned type wraps to an enormous number. Every sift-up loop must therefore be guarded by i > 0 rather than relying on the arithmetic to signal termination. That is our first pitfall, and we will meet it properly in Part 3.

Where This Goes

You now have the shape and the addressing scheme. What is missing is the ordering rule that makes the root meaningful, and the two repair routines that restore it after a change. That is Part 2 and Part 3 — and between them they account for essentially every line of code in a binary heap.