Algorithms from zero
The heap
You know trees have a shape. Now imagine a tree shaped so compactly that you can store it in an array with no pointers at all. And imagine a tree designed so that the root is always the smallest (or largest) element. No searching, no comparisons—it is right there at index 0. This is a heap. It combines two ideas: a specific shape (complete binary tree) and a specific ordering rule (heap property). Together, they enable O(1) access to the min or max, and the clever array encoding means no wasted space.
After this lesson you can explain what a complete binary tree is, state the heap property for min-heaps and max-heaps, use index arithmetic to find parent and child indices in an array-based heap, build a small heap by hand and verify the heap property holds, visualize the relationship between the tree structure and the flat array, predict where the root, min, and max live in a heap array, and recognize a heap when you see one.
What is a heap?
A heap is a binary tree that satisfies two properties:
- Shape property (complete binary tree): Every level is completely filled except possibly the last level, which is filled from left to right.
- Heap property: Every parent is less than or equal to its children (in a min-heap) or greater than or equal to its children (in a max-heap).
Together, these properties enable the root (top of the tree) to always be the smallest (min-heap) or largest (max-heap) element.
What is a complete binary tree?
A complete binary tree is a binary tree where:
- Every level except possibly the last is completely full.
- If the last level is not full, its nodes are filled from left to right (no gaps).
Example: A complete tree with 7 nodes:
1
/ \
2 3
/ \ / \
4 5 6 7All levels 0–2 are full. This is complete. If we had a tree like:
1
/ \
2 3
/ \
4 5This is NOT complete because node 3 has a right child (5) but node 2 does not have a right child.
The heap property
In a min-heap, every parent is less than or equal to its children. This means the smallest element is always at the root.
In a max-heap, every parent is greater than or equal to its children. This means the largest element is always at the root.
Example min-heap:
1 (smallest)
/ \
3 2
/ \
5 4Each parent ≤ its children: 1 ≤ (3, 2), 3 ≤ (5, 4), 2 ≤ (nothing). Min is always at the root.
The array representation
Because a heap is a complete binary tree, it can be stored in a flat array with no pointers. We simply lay the nodes out in breadth-first order (level by level, left to right). The root is at index 0.
For a node at index i:
- Parent index =
Math.floor((i - 1) / 2) - Left child index =
2 * i + 1 - Right child index =
2 * i + 2
Example: The min-heap above as an array:
Index: 0 1 2 3 4
Value: [1, 3, 2, 5, 4]Verify the relationships:
- Index 0 (value 1) has children at indices 1 (value 3) and 2 (value 2). Parent = floor((1-1)/2) = 0. Parent = floor((2-1)/2) = 0. ✓
- Index 1 (value 3) has children at indices 3 (value 5) and 4 (value 4). Parent = floor((3-1)/2) = 1. Parent = floor((4-1)/2) = 1. ✓
- Index 2 (value 2) has no children (indices 5 and 6 don’t exist). Parent = floor((2-1)/2) = 0. ✓
Why the formulas work
In breadth-first order, if you number nodes 0, 1, 2, …, the structure of a complete binary tree means:
- Node 0 is the root.
- Node 1 and 2 are the children of node 0.
- Nodes 3 and 4 are the children of node 1.
- Nodes 5 and 6 are the children of node 2.
- And so on.
The pattern is that the children of node i are at indices 2*i + 1 and 2*i + 2. Working backward, the parent of node j is at index floor((j - 1) / 2).
Building a heap from scratch
Let’s build a min-heap by hand and store it in an array:
1
// Min-heap stored as an array
2
const minHeap = [1, 3, 2, 5, 4];
3
4
// Helper functions for index arithmetic
5
function parentIndex(i) {
6
return Math.floor((i - 1) / 2);
7
}
8
9
function leftChildIndex(i) {
10
return 2 * i + 1;
11
}
12
13
function rightChildIndex(i) {
14
return 2 * i + 2;
15
}
16
17
// Access the root (the minimum in a min-heap)
18
console.log("Root (min):", minHeap[0]); // 1
19
20
// Access children of index 1 (value 3)
21
console.log("Value at index 1:", minHeap[1]); // 3
22
console.log("Left child of index 1:", minHeap[leftChildIndex(1)]); // 5
23
console.log("Right child of index 1:", minHeap[rightChildIndex(1)]); // 4
24
25
// Access parent of index 3 (value 5)
26
console.log("Value at index 3:", minHeap[3]); // 5
27
console.log("Parent of index 3:", minHeap[parentIndex(3)]); // 3
- L2 The heap is just an array. Index 0 is the root.
- L5 Parent index formula: floor((i - 1) / 2).
- L8 Left child index formula: 2*i + 1.
- L11 Right child index formula: 2*i + 2.
- L15 The root is always at index 0.
- L18 Access any node's children using the index formulas.
- L23 Navigate from a child back to its parent.
A larger heap
Build a max-heap with 10 nodes. The maximum is always at the root.
1
// Max-heap stored as an array
2
const maxHeap = [50, 30, 20, 10, 15, 8, 5, 2, 3, 7];
3
4
function parentIndex(i) {
5
return Math.floor((i - 1) / 2);
6
}
7
8
function leftChildIndex(i) {
9
return 2 * i + 1;
10
}
11
12
function rightChildIndex(i) {
13
return 2 * i + 2;
14
}
15
16
// Verify the heap property: parent >= children
17
for (let i = 0; i < maxHeap.length; i++) {
18
const left = leftChildIndex(i);
19
const right = rightChildIndex(i);
20
21
if (left < maxHeap.length) {
22
console.log(`Parent ${maxHeap[i]} >= left child ${maxHeap[left]}: ${maxHeap[i] >= maxHeap[left]}`);
23
}
24
if (right < maxHeap.length) {
25
console.log(`Parent ${maxHeap[i]} >= right child ${maxHeap[right]}: ${maxHeap[i] >= maxHeap[right]}`);
26
}
27
}
- L2 A max-heap: every parent >= its children.
- L16 Loop through every node.
- L17 Compute indices of left and right children.
- L20 If the left child exists, check the heap property.
- L23 If the right child exists, verify the parent is >= the child.
1
const minHeap = [1, 3, 2, 5, 4];
2
// Navigate from root to node at index 3
3
let current = 0; // Start at root
4
let target = 3; // Index 3 has value 5
5
// Find parent: floor((3-1)/2) = 1
Time complexity
In a heap array:
- Access root (min/max): O(1). It is always at index 0.
- Index arithmetic (parent/child lookup): O(1). A single division or multiplication.
- Access any node by index: O(1). Direct array lookup.
Space complexity
- Storing the heap: O(n), where n is the number of nodes. The array uses O(n) space, and no pointers are needed.
Note: The operations of adding or removing elements from a heap (push, pop, sift) are NOT covered in this lesson; those are the focus of the next lesson (08/02). Here, we cover only the structure and the O(1) index arithmetic.
In a complete binary tree with 7 nodes, how many nodes must be in level 0 and level 1 (the root and its children)?
In an array-based heap with the array [10, 20, 30, 40, 50], what is the parent index of the node at index 4?
In an array-based heap, what is the left child index of the node at index 2?
Which of these arrays is NOT a valid min-heap?
Why can a complete binary tree be stored in an array with no pointers?
lesson.inset.undefined
Why the heap structure matters. Many real systems need to repeatedly extract the minimum (or maximum) element—task scheduling, Dijkstra’s algorithm, median finding. A heap is the data structure that does this efficiently. No searching, no re-sorting. Just O(1) to peek, and O(log n) to add or remove (operations we cover next lesson). The complete binary tree shape ensures the tree is always balanced, and the array encoding saves space and improves cache locality.
lesson.inset.undefined
Confusing complete with full. A full binary tree is one where every node has 0 or 2 children (no node has just 1 child). A complete binary tree has all levels filled except possibly the last, filled left to right. A heap is complete, not necessarily full.
lesson.inset.undefined
Heap with 1 node. A single-node heap is valid: it is a complete binary tree (just the root) and trivially satisfies the heap property (the root has no children to violate it). The root is both the min and the max.
Explain why a heap can be stored in an array with no pointers, and how you would find the parent of a node at index i.
A heap is a binary tree with two properties: it is a complete binary tree (all levels full except possibly the last, filled left to right), and it satisfies the heap property (every parent ≤ children in a min-heap, or ≥ in a max-heap). The root is always the minimum (min-heap) or maximum (max-heap). Because of its complete shape, a heap can be stored in an array with no pointers: for a node at index i, the parent is at ⌊(i−1)∕2⌋, the left child at 2i+1, and the right child at 2i+2. This encoding saves space and enables O(1) access to the root. The structure ensures the tree is always balanced. Next: Unit 08, lesson 02 covers the operations—push, pop, and sift—that maintain the heap property when data changes.