A tree hidden in an array
A binary heap is a complete binary tree that obeys the heap property: in a min heap every parent is less than or equal to its children, so the smallest value sits at the root. Because the tree is complete, it packs neatly into an array with no pointers. For the node at index i, its children sit at indices two i plus one and two i plus two, and its parent at the floor of i minus one over two.
Keeping the property
Two repair operations maintain order.
- Sift up: after inserting at the end, swap the new value upward while it is smaller than its parent.
- Sift down: after removing the root, move the last element to the top and swap it downward with its smaller child until order returns.
Both touch only one path from root to leaf, so they are efficient.
What it powers
A heap is the standard priority queue. It gives quick access to the extreme element, supports insertion and extraction by sifting, and underlies heapsort and shortest path algorithms that repeatedly pull the next smallest item.
Key idea
A binary heap is a complete tree stored in an array where each parent dominates its children, letting sift up and sift down keep the extreme element at the root, which makes it the natural priority queue.