Algorithms from zero
Heap operations
You have a heap. Now you want to add a new element, or remove the root. When you do, the heap breaks—a parent becomes larger than its child, or the array no longer represents a complete tree. Two operations restore order: sift-up (bubble a newcomer upward past its parent) and sift-down (sink a misplaced element downward past its children). Together they keep the heap property alive. And there is a third miracle: you can turn any unordered array into a heap by sifting down every non-leaf node, in O(n) time—faster than inserting n elements one by one.
After this lesson you can insert an element into a heap with sift-up and explain why it takes O(log n) time. You can remove the root by swapping with the last element and sift-down, and explain the O(log n) cost. You can turn an arbitrary array into a valid heap by calling sift-down on every non-leaf node starting from the last one, in O(n) total time—not O(n log n). You can trace all three operations on a concrete heap array, step by step, verifying the heap property afterward.
The two fundamental operations: sift-up and sift-down
A heap is only valid if the heap property holds: every parent is ≤ its children (min-heap) or ≥ (max-heap). When you add or remove an element, this property breaks. Two operations restore it.
Sift-up (bubble-up): When a new element is added at the end of the heap array, it may be smaller (in a min-heap) than its parent. Sift-up repeatedly compares the element with its parent and swaps upward until the heap property is restored or the root is reached.
Sift-down (bubble-down): When the root is removed and the last element is moved to the root, it may be larger than its children. Sift-down repeatedly compares the element with its smaller (or larger) child and swaps downward until the heap property is restored or a leaf is reached.
Why these work: The heap property is only violated at one node at a time. Sift-up and sift-down fix exactly one parent-child pair per swap, and because the tree is balanced (height O(log n)), at most O(log n) swaps are needed.
Push (insert)
Push adds a new element to the heap.
- Append the new value to the end of the heap array.
- Call sift-up on the newly added element.
- Sift-up stops when the new element is in the correct position (heap property restored) or reaches the root.
Example: Push 0 into the min-heap [1, 3, 2, 5, 4].
- Append: [1, 3, 2, 5, 4, 0]
- Sift-up from index 5 (value 0):
- Parent at index (5-1)/2 = 2 (value 2).
- 0 < 2, swap: [1, 3, 0, 5, 4, 2].
- Now at index 2 (value 0), parent at index (2-1)/2 = 0 (value 1).
- 0 < 1, swap: [0, 3, 1, 5, 4, 2].
- Now at index 0 (root), stop.
- Result: [0, 3, 1, 5, 4, 2]. Heap property verified: 0 ≤ (3, 1), 3 ≤ (5, 4), 1 ≤ (2). ✓
Pop (extract-min or extract-max)
Pop removes and returns the root (the min or max element).
- Save the root value (to return it).
- Move the last element in the array to the root position.
- Remove the last element from the array (size decreases by 1).
- Call sift-down on the root.
- Sift-down stops when the heap property is restored or a leaf is reached.
Example: Pop from the min-heap [1, 3, 2, 5, 4].
- Save root 1 (to return).
- Move last element (4) to root: [4, 3, 2, 5].
- Sift-down from index 0 (value 4):
- Children at indices 1 (value 3) and 2 (value 2). Smaller child is 2 at index 2.
- 4 > 2, swap: [2, 3, 4, 5].
- Now at index 2 (value 4), children at indices 5 and 6 (don’t exist).
- Stop.
- Result: [2, 3, 4, 5]. Heap property verified: 2 ≤ (3, 4), 3 ≤ (5). ✓ Returned value: 1.
Build-heap (heapify)
You can build a valid heap from an arbitrary array in O(n) time—faster than calling push n times (which would be O(n log n)).
Build-heap (a.k.a. heapify) works by sifting down every non-leaf node, starting from the last non-leaf and working backward to the root.
The last non-leaf node is at index ⌊n/2⌋ - 1. Why? Because a heap with n elements has height ⌈log₂(n+1)⌉, and the last non-leaf is the last node whose children exist.
For each non-leaf, call sift-down. Even though sift-down is O(log n) per node, build-heap is O(n) total because most nodes are leaves (which take O(1) time), and internal nodes near the bottom have short subtrees.
Example: Turn [5, 3, 8, 1, 4] into a min-heap.
- n = 5. Last non-leaf index = ⌊5/2⌋ - 1 = 1.
- Sift-down index 2 (value 8): No children (indices 5, 6 don’t exist). No swap.
- Sift-down index 1 (value 3):
- Children at indices 3 (value 1) and 4 (value 4). Smaller is 1 at index 3.
- 3 > 1, swap: [5, 1, 8, 3, 4].
- Now at index 3, no children. Stop.
- Sift-down index 0 (value 5):
- Children at indices 1 (value 1) and 2 (value 8). Smaller is 1 at index 1.
- 5 > 1, swap: [1, 5, 8, 3, 4].
- Now at index 1, children at indices 3 (value 3) and 4 (value 4). Smaller is 3 at index 3.
- 5 > 3, swap: [1, 3, 8, 5, 4].
- Now at index 3, no children. Stop.
- Result: [1, 3, 8, 5, 4]. Heap property verified: 1 ≤ (3, 8), 3 ≤ (5, 4). ✓
Sift-up in code
1
function siftUp(heap, index) {
2
// Repeatedly swap with parent until heap property holds or root is reached
3
while (index > 0) {
4
const parentIndex = Math.floor((index - 1) / 2);
5
// In a min-heap, child < parent is a violation; swap and continue
6
if (heap[index] < heap[parentIndex]) {
7
[heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]];
8
index = parentIndex;
9
} else {
10
break; // Heap property restored
11
}
12
}
13
}
14
15
function push(heap, value) {
16
heap.push(value);
17
siftUp(heap, heap.length - 1);
18
}
- L1 Sift-up restores the heap property after insertion.
- L3 Continue while the node is not the root.
- L4 Compute parent index using the standard formula.
- L6 In a min-heap, if child < parent, the property is violated.
- L7 Swap child with parent and move up.
- L10 Push appends the value to the end and sifts it up.
Sift-down in code
1
function siftDown(heap, index) {
2
// Repeatedly swap with the smaller (or larger) child until the property holds
3
while (true) {
4
const leftChild = 2 * index + 1;
5
const rightChild = 2 * index + 2;
6
let smallest = index;
7
8
// Check if left child exists and is smaller than the current smallest
9
if (leftChild < heap.length && heap[leftChild] < heap[smallest]) {
10
smallest = leftChild;
11
}
12
13
// Check if right child exists and is smaller
14
if (rightChild < heap.length && heap[rightChild] < heap[smallest]) {
15
smallest = rightChild;
16
}
17
18
// If a child is smaller, swap and continue; otherwise, stop
19
if (smallest !== index) {
20
[heap[index], heap[smallest]] = [heap[smallest], heap[index]];
21
index = smallest;
22
} else {
23
break; // Heap property restored
24
}
25
}
26
}
27
28
function pop(heap) {
29
const root = heap[0];
30
heap[0] = heap[heap.length - 1];
31
heap.pop();
32
if (heap.length > 0) {
33
siftDown(heap, 0);
34
}
35
return root;
36
}
- L1 Sift-down restores the heap property after removing the root.
- L4 Compute indices of the left and right children.
- L5 Track the index of the smallest element (for min-heap).
- L8 If left child exists and is smaller, update smallest.
- L13 Check right child in the same way.
- L18 If smallest is not the current node, a swap is needed.
- L19 Swap and continue sifting from the new position.
- L24 Pop returns the root and restores the heap property.
Build-heap in code
1
function buildHeap(arr) {
2
// Start from the last non-leaf node and sift down each
3
const lastNonLeaf = Math.floor(arr.length / 2) - 1;
4
for (let i = lastNonLeaf; i >= 0; i--) {
5
siftDown(arr, i);
6
}
7
return arr;
8
}
9
10
// Example: turn an unordered array into a min-heap
11
const unordered = [5, 3, 8, 1, 4];
12
buildHeap(unordered);
13
console.log("Heap:", unordered); // [1, 3, 8, 5, 4]
- L1 buildHeap transforms any array into a valid heap.
- L3 Last non-leaf node is at index floor(n/2) - 1.
- L4 Iterate from the last non-leaf down to the root (index 0).
- L5 Sift down each node to restore the heap property in its subtree.
- L11 buildHeap is O(n) because most nodes are leaves (O(1) sift) and internal nodes have short subtrees.
1
const minHeap = [1, 3, 2, 5, 4];
2
// Push 0
3
minHeap.push(0); // [1, 3, 2, 5, 4, 0]
4
// Sift-up from index 5
1
const minHeap = [1, 3, 2, 5, 4];
2
// Pop the root (1) and sift down
Sift-up and sift-down time complexity
Sift-up moves the element upward one level per swap. A min-heap with n elements has height ⌈log₂(n+1)⌉, so at most O(log n) swaps occur. Each swap is O(1) (two comparisons, one array access).
- Time: O(log n)
Sift-down moves the element downward one level per swap, also O(log n) in the worst case.
- Time: O(log n)
Push and pop
Push appends (O(1)) and calls sift-up (O(log n)).
- Time: O(log n)
Pop moves the last to the root (O(1)), removes the last (O(1)), and sifts down (O(log n)).
- Time: O(log n)
Build-heap time complexity: why O(n) and not O(n log n)?
A naive approach would call push n times: O(n log n). But build-heap works differently. It calls sift-down on n/2 nodes. This seems like O(n * log n), but it is not.
The key insight: sift-down from a node at height h takes O(h) time (not O(log n) for all nodes). A heap has:
- 1 node at height ⌈log₂ n⌉ (the root).
- 2 nodes at height ⌈log₂ n⌉ - 1.
- 4 nodes at height ⌈log₂ n⌉ - 2.
- …
- n/2 nodes at height 0 (the leaves).
Total work:
1*⌈log₂ n⌉ + 2*(⌈log₂ n⌉ - 1) + 4*(⌈log₂ n⌉ - 2) + ... + (n/2)*0
= Σ(2^h * (⌈log₂ n⌉ - h)) for h from 0 to ⌈log₂ n⌉This sum equals n * (constant that depends on the logarithm), which converges to a constant < 2. Therefore, time is O(n).
- Build-heap: O(n)
Space complexity
All three operations (push, pop, build-heap) work in place. The heap is stored in a single array.
- Space: O(1) (not counting the array itself)
After pushing a new element into a min-heap, sift-up stops when the element is at a position where its value is greater than its parent's value. How many swaps might be needed in the worst case for a heap with 1000 elements?
You have a min-heap with 16 elements. What is the index of the last non-leaf node when you call build-heap?
Why is build-heap O(n) instead of O(n log n)?
You pop the root from the min-heap [1, 4, 2, 7, 5]. The standard pop moves the last element to the root, then sifts down. What is the resulting heap array?
After applying build-heap to [10, 5, 20, 15, 30], what is the minimum value at the root of the resulting min-heap?
lesson.inset.undefined
Why heap operations matter. Push and pop are O(log n), which is much faster than adding to the end of a sorted list (O(n) because you must shift all larger elements). Build-heap in O(n) means you can take any dataset and prepare it for efficient priority queue operations. Dijkstra’s algorithm, task scheduling, and median finding all rely on these operations.
lesson.inset.undefined
Confusing sift directions. Sift-up is for insertion (start at leaf, move toward root). Sift-down is for deletion (start at root, move toward leaves). They restore the property in different directions, so the logic is not symmetric. Check your code: sift-up goes upward (parent = (i-1)/2), sift-down goes downward (children = 2i+1, 2i+2).
lesson.inset.undefined
Single element heap. Pushing into an empty heap or a heap with one element works fine: the new element is appended, and sift-up stops immediately because the parent condition is not violated. Popping from a heap with one element leaves an empty heap; sift-down should not be called if the heap is empty.
Explain the difference between sift-up and sift-down, and when you use each one.
To maintain a heap while adding or removing elements, use two operations: sift-up (bubble a new element upward by comparing and swapping with its parent, O(log n)) and sift-down (sink a misplaced element downward by comparing and swapping with its smaller/larger child, O(log n)). Push appends a new value and sifts up; pop extracts the root, moves the last element to the root, and sifts down—both O(log n). The miracle operation is build-heap (a.k.a. heapify): sift down every non-leaf node starting from the last one, turning any array into a valid heap in O(n) total time. This is faster than pushing n elements one by one (O(n log n)) because most nodes are leaves (O(1) work) and internal nodes have shallow subtrees. The total work is the sum of node-count × depth, which converges to O(n). Next: Unit 08, lesson 03 uses heaps to build priority queues, the foundational data structure for Dijkstra’s algorithm and task scheduling.