Heap (Binary)

A complete tree where every parent beats its children, packed into a plain array with no pointers.

A binary heap is a tree built for one job: *always knowing the most extreme item*. Every parent beats both its children — smaller in a min-heap, larger in a max-heap — so the winner is always sitting at the very top, one glance away. Crucially, a heap is not fully sorted: only the root is guaranteed extreme. That weaker promise is exactly what makes it cheap to maintain.

A tree with no pointers

Because a heap is a complete tree — filled level by level, left to right, with no gaps — it packs perfectly into a plain array. The node at index i finds its children at 2i+1 and 2i+2, and its parent at (i-1)/2. No node objects, no left/right links: just arithmetic on an array.

The two repair moves

Every operation keeps the heap property (each parent beats its children) using one of two moves:

1Sift up (insert): append the new item at the end of the array, then swap it with its parent repeatedly while it beats that parent — bubbling it up to its rightful level.
2Sift down (extract): the top item is the answer; move the *last* item into the root slot, then swap it down with its better child repeatedly until the rule holds again.

Worked example — a min-heap

Insert 5, 3, 8, 1 into a min-heap. Each insert sifts up; the smallest always ends on top:

insert 5            -> [5]
insert 3 (3<5 swap) -> [3, 5]
insert 8            -> [3, 5, 8]
insert 1 (1<5, 1<3) -> [1, 3, 8, 5]

        1
      /   \
     3     8
    /
   5    (root is the minimum)

extract-min: take 1, move 5 to root, sift down -> [3, 5, 8]

Build a heap in O(n), not O(n log n)

You don't have to insert items one at a time. Given an array, sift *down* from the last parent up to the root — this heapify trick builds the whole heap in O(n) time, beating n separate O(log n) inserts.

Don't expect sorted output for free

Reading a heap's array left to right is not sorted. To get sorted order you must repeatedly extract-min — which is exactly heapsort, an O(n log n) algorithm. The heap only ever guarantees the *root*.

OperationTimeSpace

peek (find extreme) · always the rootO(1)O(1)

insert · sift up one pathO(log n)O(1)

extract-min/max · sift down one pathO(log n)O(1)

build-heap (heapify) · sift down from last parentO(n)O(1)

Check yourself

After removing the root of a heap, how is the heap property restored?