A heap is a tree stored in an array. Not a tree with an array beside it — the array IS the tree.

Where the pointers went

In lessons 11 and 12 a node held two pointers and its children were wherever those pointers led. Here there are none, because a child's position is computed:

for the node at index i:
    parent  (i−1)/2
    left     2i+1
    right    2i+2

index:     0   1   2   3   4   5   6
value:    12  19  15  41  22  17  33

                12
              /    \
            19      15
           /  \    /  \
         41   22  17   33

The same tree, drawn two ways. The second is simply the first read out level by level.

Cost in pointers: 0 bytes. Lesson 11's node cost 88 bytes and lesson 12's 96, and each sat wherever the allocator put it. Here every element sits contiguously, one after another, and the processor pulls them in batches.

In lesson 11 you measured what scattered pointers cost: the same 5000.5 comparisons and 4.5× the time. Here that same observation runs the other way.

The heap property

No parent is larger than its children.

That is all. Nothing about left versus right — there is NO order between siblings. Above, 19 > 15, and that is a perfectly valid heap.

Exactly one thing follows: the smallest element is a[0]. Always. With no search and no comparison. And it knows nothing else — step 5 is about why that is enough.

Insertion: sift up

Push(item):
    append item at the end of the array
    i ← len(a) − 1
    while i > 0:
        p ← (i−1)/2
        c.Hit()
        if a[p] ≤ a[i]: stop        // parent no larger — in order
        swap a[p] and a[i]
        i ← p

The new element goes into the one free slot and rises until its parent is no larger. The path to the root is log2 n long, so O(log n).

Taking the top: sift down

Pop():
    top ← a[0]
    a[0] ← the last element; shorten the array
    i ← 0
    loop:
        find the smallest of a[i], a[2i+1], a[2i+2]     // 2 comparisons
        if the smallest is a[i]: stop
        swap them; i ← the smallest one's index
    return top

The last element travels to the root — the only way not to leave a hole in the array — and sinks until both children are no smaller.