Heap operations
Push, pop, and build-heap: how to mutate a heap while keeping the heap property. Sift-up and sift-down restore order. Build-heap turns any array into a heap in O(n) time—not O(n log n).
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.
Why not simply re-sort the array after every change? Because re-sorting costs O(n log n) and destroys the heap structure. Sift-up and sift-down exploit the fact that only one parent-child relationship is violated at a time, so they fix it locally and cheaply.
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). ✓
Together, these three steps — start from the last non-leaf, sift each one down, work toward the root — guarantee the whole array becomes a valid heap. Skip any non-leaf node and you could leave a subtree with a violated parent-child pair.
Sift-up in code
function siftUp(heap, index) { // Repeatedly swap with parent until heap property holds or root is reached while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); // In a min-heap, child < parent is a violation; swap and continue if (heap[index] < heap[parentIndex]) { [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]]; index = parentIndex; } else { break; // Heap property restored } } } function push(heap, value) { heap.push(value); siftUp(heap, heap.length - 1); } - 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
function siftDown(heap, index) { // Repeatedly swap with the smaller (or larger) child until the property holds while (true) { const leftChild = 2 * index + 1; const rightChild = 2 * index + 2; let smallest = index; // Check if left child exists and is smaller than the current smallest if (leftChild < heap.length && heap[leftChild] < heap[smallest]) { smallest = leftChild; } // Check if right child exists and is smaller if (rightChild < heap.length && heap[rightChild] < heap[smallest]) { smallest = rightChild; } // If a child is smaller, swap and continue; otherwise, stop if (smallest !== index) { [heap[index], heap[smallest]] = [heap[smallest], heap[index]]; index = smallest; } else { break; // Heap property restored } } } function pop(heap) { const root = heap[0]; heap[0] = heap[heap.length - 1]; heap.pop(); if (heap.length > 0) { siftDown(heap, 0); } return root; } - 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
function buildHeap(arr) { // Start from the last non-leaf node and sift down each const lastNonLeaf = Math.floor(arr.length / 2) - 1; for (let i = lastNonLeaf; i >= 0; i--) { siftDown(arr, i); } return arr; } // Example: turn an unordered array into a min-heap const unordered = [5, 3, 8, 1, 4]; buildHeap(unordered); 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.
const minHeap = [1, 3, 2, 5, 4]; // Push 0 minHeap.push(0); // [1, 3, 2, 5, 4, 0] // Sift-up from index 5 const minHeap = [1, 3, 2, 5, 4]; // 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. Now when you need to mutate a heap, you know exactly which direction to sift: insertion goes up, removal goes down — and build-heap always runs bottom-up.
Practice
Start at the top. Tasks go easiest → hardest: recall a fact, apply it to a case, then a senior-level stretch. Open one, attempt it, then reveal.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.