A Complete Binary Tree Stored in a Plain Array
Introduction to Binary Heaps
A binary heap is a complete binary tree that satisfies the heap property, stored compactly in an array using simple index arithmetic — no pointers needed.
What you'll learn
- Describe the complete-tree shape and why it enables array storage
- State the heap property and distinguish it from BST ordering
- Derive the parent and child index formulas from first principles
A binary heap is one of the most practical data structures in computer science. It powers priority queues, heap sort, graph shortest-path algorithms, and streaming statistics — all without a single pointer or linked node.
What Makes a Tree a Heap?
Two rules define a binary heap:
Rule 1 — Complete binary tree. Every level is fully filled except possibly the last, and the last level is filled left-to-right. This shape guarantees the tree height is always ⌊log₂ n⌋.
Rule 2 — Heap property. Every node satisfies an ordering constraint with respect to its children. In a min-heap every parent is less than or equal to both children; in a max-heap every parent is greater than or equal to both children. Note: siblings have no guaranteed order relative to each other — the heap property is only between a node and its direct children.
Storing the Tree in an Array
Because the tree is always complete, there are no gaps. You can lay the nodes level-by-level into an array and recover the tree structure entirely from the index:
| Relationship | Formula |
|---|---|
Parent of node i | (i - 1) >> 1 |
Left child of node i | 2 * i + 1 |
Right child of node i | 2 * i + 2 |
The root lives at index 0. Its left child is at 1, right child at 2. Node 1’s children are at 3 and 4; node 2’s children are at 5 and 6, and so on.
// Verify the formulas for a small heap
const heap = [1, 3, 2, 7, 4, 5, 6]; // min-heap
function parent(i) { return (i - 1) >> 1; }
function left(i) { return 2 * i + 1; }
function right(i) { return 2 * i + 2; }
console.log(parent(3)); // 1 — node 7's parent is node 3 ✓
console.log(left(1)); // 3 — node 3's left child is node 7 ✓
console.log(right(1)); // 4 — node 3's right child is node 4 ✓Why Not a BST?
A binary search tree gives you O(log n) search but provides no O(1) minimum or maximum. A heap gives you the extreme value instantly (it is always at index 0) but does not support arbitrary key lookup. Choose based on what your algorithm needs: ordered traversal → BST; repeated min/max extraction → heap.
Complexity at a Glance
| Operation | Time |
|---|---|
| Peek min/max | O(1) |
| Push | O(log n) |
| Pop min/max | O(log n) |
| Build from array | O(n) |
| Search | O(n) |
Up Next
Learn how min-heaps and max-heaps differ, and implement sift-up and sift-down to keep the heap property intact after every push and pop.
Min-Heap and Max-Heap →