Shape and order
A binary heap is a complete binary tree, filled level by level with no gaps, that obeys the heap property: in a min heap every parent is smaller than its children, so the minimum sits at the root. A max heap mirrors this for the maximum.
Packed in an array
The complete shape lets a heap live in a plain array with no pointers. For the node at index i, its children sit at index two i plus one and two i plus two, and its parent at index i minus one over two. This index arithmetic replaces tree links entirely.
The two core moves
Every operation reduces to two repair routines:
- Sift up is used after insert. The new element is appended at the end, then swapped upward while it is smaller than its parent until the heap property holds.
- Sift down is used after removing the root. The last element is moved to the root, then swapped downward with its smaller child until order is restored.
Because the tree is complete, its height is small, so each repair touches only a short path from root to leaf.
Key idea
A binary heap is a complete tree packed in an array where sift up after insert and sift down after removal restore the parent child order along one short path.